黑马程序员技术交流社区

标题: 新人报到_学习分享 [打印本页]

作者: Vaugely 时间: 2018-5-20 22:27
标题: 新人报到_学习分享
本帖最后由 Vaugely 于 2018-5-20 22:35 编辑

大家好我是java 89期学员~给大家分享一下布尔质数筛选法质数算法主要作用于应用程序加密领域,因为它的无序,无规则,所以给程序加密破解难度极大.
因为质数是没有规律的,而计算机擅长于计算有规律的东西,我们可以换一个思路,让电脑去选则非质数,
其实就是让电脑去遍历合数,那么把合数设为true,剩下的就全都是质数了.源代码在下面,大家可以尝试运行下~
import java.util.Scanner;
// import java.util.concurrent.TimeUnit;

public class 质数算法
{
      public static void main (String [] args)
      {

            System.out.println("\n");
            System.out.println("请输入你需要计算质数的范围: (请勿输入超过20亿的数字)");
            Scanner cr=new Scanner(System.in);
            int n=cr.nextInt();
            //素数筛选法通过bool数组来把非质数筛选掉
            boolean[] num=new boolean[n+1];
            //先制定两个非质数 0 和1
            int n2 = 2;
            num[0] = true;
            num[1] = true;
            //程序计时开始
            long startTime = System.currentTimeMillis();
            //以取余的思路，被除数只需要到递增到除数的平方根即可
            for (int i = 2; i * i < n + 1; i++)
            {
                     //如果这个数没有被标记为非质数那么就进行推算
                     if (!num)
                     {
                              for (int j = i; j <= n - i; j += i)
                              {
                                    if (!num[j + i])
                                    {
                                             //此处把推算的非质全部设为true
                                             num[j + i] = true;
                                             //用于统计非质
                                             n2++;
                                    }
                              }
                     }
            }
            long endTime = System.currentTimeMillis();

            System.out.println("\n");
            System.out.println(n+"中的质数个数为"+(n - n2 + 1));
            System.out.println("计算用时：" + (endTime - startTime) + "ms");
            System.out.println("需要输出这些质数吗? Y/N");
            String ok=cr.next();

            if(ok.equals("y")|ok.equals("Y"))
            {
                     for (int i = 0; i < n + 1; i++)
                     {
                              if (!num)
                              {
                                    System.out.print(i+" ");
                              }
                     }
            }
      }
}

作者: adawan 时间: 2018-5-22 11:02
同学你调皮了

作者: 小yuer 时间: 2018-5-25 13:50
不错不错，再接再厉~~

作者: gzgd 时间: 2019-3-12 11:07
不错不错

作者: gzgd 时间: 2019-3-12 11:07