起航学习网

IT培训网Java开发培训学员讲解2种查找素数的方法：

题目大概的意思是： 查找2～N范围内所有的素数。

题意简单，粗暴。

首先需要考虑，一个数字需要怎么判断它是否是素数？
普及一下素数的概念：除了 1 和 它本身外没有能被整除的数，我们称为素数。
以数字 7为例：   int su = 7;  给 su 贴一个标签 假设是素数，boolean flag = true;
然后我们根据素数的概念可以写出一下循环：
for(int i = 2; i < su; i++){
    if(su%i==0)  {//有可以被整除的数字，说明su不是素除这时候我们就需要做两件事情
        //1. 需要把su的标记改成false说明它不是素数
        flag = false;
        //2. 然后跳出循环，因为有一个可以被整除就说明它不是素数了，继续判断下去没有意义。
         break;
    }
}
当学会判断某个数字是否为素数后，查找2～N范围内的素数就容易很多，因为我们直到for就是重复干相同一件事情的。所以外层嵌套一个for就可以了。
for(int su = 2; su < N; su++){
    for(int i = 2; i < su; i++){
        if(su%i==0)  {//有可以被整除的数字，说明su不是素除这时候我们就需要做两件事情
            //1. 需要把su的标记改成false说明它不是素数
            flag = false;
            //2. 然后跳出循环，因为有一个可以被整除就说明它不是素数了，继续判断下去没有意义。
             break;
        }
    }

   if(flag){
      //如果flag = true 则说明su为素数，直接输出就好了。
      System.out.println(su);
   }
}
小提示：判断一个数字不许要判断到它本身减1，实践证明 判断到它的平方跟即可。
所以判断素数的条件可以写为：
for(int i = 2; i <= Math.sqrt(su); i++)
改写后的方法效率会快很多，但是还不能满足我们的要求。（假设寻找一千万以内的素数，没有优化的方法需要很久，优化后的方法大概需要13秒）
但是楼主非要没有人性，想查找1亿以内的素数！！！
以上方法虽然可以，但是效率一般。下面介绍一种更好的查找素数方法：
我们知道如果2是素数，那么2的倍数就不是素数；3是素数，3的倍数就不是素数。
基于这种想法我们就有了这第二种方法：
先定义一个boolean类型的数组，用下标表示自然数0，1，2，3....N
用数组里的内容来标记它是否为素数，是素数就true 不是则为false；初始时假设全是素数，当碰到第一个素数（2）的时候把它的倍数标记为false
boolean[] prime = new boolean[N];
//把数字全标记为true表示假设全为素数。
for(int i = 2; i < prime.length;i++){
    prime = true;
}

/也可以用数组自带的fill方法，填充要简单的多。fill(要填充的数组，要填充的内容)

接下来就是实现查找素数：

for(int i = 2; i < prime.length; i++){

if(prime){ //如果为真，则需要标记它的倍数为false

for(int j = 2*i; j < prime.length; j+=2){ // 大家可以想想 j *= 2 为何是错的。

prime[j]=false;

}

}

}

这样就完成了素数的查找，输出的时候。只需判断boolean数组就可以了，当数组内容为true则输出它的下标。

基于这种思想，可以做一个和素数有关的题: 将一个偶数分解称质因数相乘的形式 ，例如 ： 90 = 2 * 3 * 3 *5

利用编程解决问题，会让人体会到成功的快感。 不说了，敲代码去了。

文章出自：http://qh.itpxw.cn/peixun/software/202190808.html

文章标题：讲解2种查找素数的方法



免责声明：本站文章均由入驻起航学习网的会员所发或者网络转载，所述观点仅代表作者本人，不代表起航学习网立场。如有侵权或者其他问题，请联系举报，必删。侵权投诉

(责任编辑：深圳学历教育网)