[论坛提问] java在三秒内筛出1亿范围内的素数，能力有限无法继续优化

今天研究了快一下午，终于由刚开始筛不出来到100秒到十秒，再优化算法到5秒再到现在只需要3秒，，

可是一些玩C的终极大神半秒就能搞定。。好郁闷，，，
下面是我的实现代码：

package cn.wangzhe.test;
import java.util.*;
public class GetPrimeNumber
{
public static void main(String[] args){
final int MAX=100000000;
long start = System.currentTimeMillis();
int[] arr=getPrimeNumArray(MAX);
long end = System.currentTimeMillis();
System.out.println("数组筛法："+(end-start)+"ms");
//System.out.println(Arrays.toString(arr));
start = System.currentTimeMillis();
arr=getPrimeNumArray2(MAX);
end = System.currentTimeMillis();
System.out.println("数组筛法2："+(end-start)+"ms");
/*for(int i=0;i<list.size();i++){
}
System.out.println(true);*/
}
/*这里我们来讨论一下用“筛法”来解决这个问题。
　　　先来举个简单的例子来介绍一下“筛法”，求2~20的质数，它的做法是先把2~20这些数一字排开：
　　　2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
　　　先取出数组中最小的数，是2，则判断2是质数，把后面2的倍数全部删掉。
　　　2 | 3 5 7 9 11 13 15 17 19
　　　接下来的最小数是3，取出，再删掉3的倍数
　　　2 3 | 5 7 11 13 17 19
　　　一直这样下去，直到结束。剩下的数都是素数。
　　　筛法的原理是：
　　　1.数字2是素数。
　　　2.在数字K前，每找到一个素数，都会删除它的倍数，即以它为因子的整数。
如果k未被删除，就表示2->k-1都不是k的因子，那k自然就是素数了。
　　　(1)除余法那篇文章里也介绍了，要找出一个数的因子，其实不需要检查2->k，
只要从2->sqrt(k)，就可以了。所有，我们筛法里，其实只要筛到sqrt(n)就已经找出所有的素数了，其中n为要搜索的范围。
　　　(2)另外，我们不难发现，每找到一个素数k，就一次删除2k, 3k, 4k,..., ik，不免还是有些浪费，
因为2k已经在找到素数2的时候删除过了，3k已经在找到素数3的时候删除了。因此，当i＜k时，
都已经被前面的素数删除过了，只有那些最小的质因子是k的那些数还未被删除过，所有，就可以直接从k*k开始删除。
　　　(3)再有，所有的素数中，除了2以外，其他的都是奇数，那么，当i时奇数的时候
，ik就是奇数，此时k*k+ik就是个偶数，偶数已经被2删除了，
所有我们就可以以2k为单位删除步长，依次删除k*k, k*k+2k, k*k+4k, ...。
*/
//数组筛法
public static int[] getPrimeNumArray2(int max) {
boolean[] flag=new boolean[max];
int gab = 4;
flag[4]=true;
for(int i=5;i<=Math.sqrt(max);i += gab ^= 6)
for(int j=i*i;j<max;j+=2*i)
flag[j]=true;
int[] primeArray=new int[16];
int len=0;
for(int i=2;i<flag.length;i++){
if(!flag[i]){
primeArray[len++]=i;
primeArray = sureArraylen(primeArray, len);
}
}
int[] result=new int[len];
System.arraycopy(primeArray, 0, result, 0, len);
return result;
}
public static int[] getPrimeNumArray(int max) {
boolean[] flag=new boolean[max];
for(int j=2*2;j<max;j+=2)
flag[j]=true;
for(int i=3;i<=Math.sqrt(max);i++)
for(int j=i*i;j<max;j+=2*i)
flag[j]=true;
//return null;
int[] primeArray=new int[16];
int len=0;
for(int i=2;i<flag.length;i++){
if(!flag[i]){
primeArray[len++]=i;
primeArray = sureArraylen(primeArray, len);
}
}
int[] result=new int[len];
System.arraycopy(primeArray, 0, result, 0, len);
return result;
}
public static int[] sureArraylen(int[] primeArray, int len) {
if(len==primeArray.length){
int[] temp=new int[primeArray.length*2+2];
System.arraycopy(primeArray, 0, temp, 0, len);
primeArray=temp;
}
return primeArray;
}
/*
* (5)由(2)可知，如果每找到一个素数k，能依次只删除以k为最小素数因子的数，
* 那么每个数字就都只被删除一次，那这个筛法就能达到线性的O(n)效率了。
* 比如数字600 = 2*2*3*5*11，其中2是它的最小素数因子。那这个数就被2删除了。
* 3、5、11虽然都是它的因子，但不做删除它的操作。要实现这种策略，那每找到一个素数k，
* 那从k开始，一次后面未被删除的数字来与k相乘，删除它们的积。比如要筛出2～60之间的素数：
　　　1.先列出所有的数。
　　　2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 50 51 52 53 54 55 56 57 58 59 60
　　　2.选出序列中的第一个数，即2，判断它是素数，然后从2开始，依次与剩下的未被删除的数相乘，
删除它们的积。即2*2=4， 2*3=6，2*4=8...。
　　　2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 50 51 52 53 54 55 56 57 58 59 60
　　　02 | 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59
　　　3.去掉2后，再选出序列中第一个数，即3，判断它是素数，然后从3开始，依次与剩下的数相乘，即3*3=9，3*5=15，3*7=21...
　　　02 | 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59
　　　02 03 | 05 07 11 13 15 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59
　　　4.去掉3后，选出最小的数5，为素数，依次删除5*5=25，5*7=35，5*11=55，...
　　　02 03 | 05 07 11 13 15 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59
　　　02 03 05 | 07 11 13 15 17 19 23 29 31 37 41 43 47 49 53 59
　　　5.去掉5后，选出最小的数7，为素数，删除7*7=49，...
　　　02 03 05 | 07 11 13 15 17 19 23 29 31 37 41 43 47 49 53 59
　　　02 03 05 | 07 11 13 15 17 19 23 29 31 37 41 43 47 53 59
　　　6.去掉7后，第一个数11的平方121大于60，所以结束。剩下的数字全为素数。
　　　02 03 05 07 11 13 15 17 19 23 29 31 37 41 43 47 53 59 |
　　　上面的操作效率很高，但在计算机中模拟的时候却又很大的障碍：
　　　首先，计算机内存是一维的空间，很多时候我们不能随心所欲，要实现上面的算法，
要求这个数据结构既能很高效地查找某个特定的值，又能不费太大代价对序列中的元素进行删除。
高效地查找，用数组是最合适的了，能在O(1)的时间内对内存进行读写，但要删除序列中一个元素却要O(n)；
单链表可以用O(1)的时间做删除操作，当然要查找就只能是O(n)了。所以这个数据结构很难找。
　　　其次，筛法的一个缺点就是空间浪费太大，典型的以空间换时间。如果我们对数组进行压缩，
比如初始时就排除了所有偶数，数组0对应数字1，1对应3，...。这样又会因为多了一道计算数字下标的工序而浪费时间。
这又是一个矛盾的问题。
　　　也许我们可以试试折中的办法：数据结构综合数组和链表2种，数组用来做映射记录，链表来记录剩下的还未被删除的数据，
而且开始也不必急着把链表里的节点释放掉，只要在数组里做个标记就可以了。下次遍历到这个数字时才删除。
这样为了删除，可以算只遍历了一次链表，不过频繁地使用free()函数，也许又会减低效率。总之，我们所做的，
依然是用空间来换时间，记录更多的信息，方便下次使用，减少再次生成信息所消耗的时间。
*/
/*public static int[] getPrimeNumArray3(int max) {
boolean[] flag=new boolean[max];
for(int i=2;i<max;i++){
for(int j=i;!flag[j]&&i*j<max;j++)
flag[i*j]=true;
}
int[] primeArray=new int[16];
int len=0;
for(int i=2;i<flag.length;i++){
if(!flag[i]){
primeArray[len++]=i;
primeArray = sureArraylen(primeArray, len);
}
}
int[] result=new int[len];
System.arraycopy(primeArray, 0, result, 0, len);
return result;
}*/
public static List<Integer> getPrimeNumList(int max) {//集合筛法
List<Integer> src=new LinkedList<Integer>();//创建一个集合进行筛
List<Integer> result=new LinkedList<Integer>();//保存筛出的素数
//初始化集合
src.add(2);
for(int i=3;i<=max;i+=2)
src.add(i);
Integer a=null;//初始化除数
while(src.size()>0){//如果第一个集合内还有值就继续筛
a=src.remove(0);//删除第一个集合中最小的数，这个数一定是素数
for(int i=0;i<src.size();i++)//删除集合中这个数的倍数
if(src.get(i)%a==0)
src.remove(i);
result.add(a);//将这个素数加入集合2
}
return result;
}
}

复制代码

思路来源：http://blog.csdn.net/controlfate/article/details/6758202

zzlin · zzlin

看不懂。。

as604049322 · as604049322

zzlin 发表于 2015-5-18 18:12
看不懂。。

这个需要大神中的大神才能看懂并优化

zzlin · zzlin

as604049322 发表于 2015-5-18 18:15
这个需要大神中的大神才能看懂并优化

确实如此

qinpeiwei881211 · qinpeiwei881211

我擦直接懵了:L

as604049322 · as604049322

我擦，这么屌的算法，居然没人看。。。

灯火通明 · 灯火通明

还不错。

帐号		自动登录	找回密码
密码			加入黑马

[论坛提问] java在三秒内筛出1亿范围内的素数，能力有限无法继续优化

6 个回复

优秀作者