【热点话题】

讲解2种查找素数的方法

发布：达内
来源：达内
时间：2015-10-13 14:41

达内 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

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