首页 > 代码库 > 写程序求素数的比较快的方法

写程序求素数的比较快的方法

今天在百度知道看见有人求算100000之内素数的方法,看了一下回帖,发现都是做C1时用烂的方法,即两个for循环,复杂度为power(n,1.5);

但是突然想到一种优化:

public static void main(String[] args){  
  int[] r = new int[10000];
  int num=0;
  int count = 0;
  
  for(int i=2;i<100000;i++){
   boolean is = true;
   if(num==0){
    r[num++] = i;
    continue ;
   }
   for(int j=0;j<num&&r[j]*r[j]<=i;j++){
    if(i%r[j]==0){
     is = false;
     break;
    }
   }
   if(is){
    System.out.print(i+"  ");
    count++;
    r[num++] = i;
   }
   if(count==5){
    System.out.println();
    count=0;
   }
  }
 }

在 计算时记录素数,并在判断是否是素数时直接将要判断的数除以记录过的素数,而不是除以所有小于该数的开方,其复杂度是肯定不大于power(n,1.5) 的,而且n越大,这种算法的优势越明显。在计算100000内素数时,时间是前者的10%(不包括输出结果,若要输出结果,平均时间大概是前者的80%)

总的来说这还只是一种比较低级的优化,应该当时早有同学想到了。

写程序求素数的比较快的方法