[算法刷题] java求质数的4种方法

第一种：双重for循环 使除数与被除数个个计算，效率极低

publicvoidtest1(intn){
longstart=System.currentTimeMillis();//取开始时间
intnum=0;
booleansign;
for(inti=2;i<n;i++){
if(i%2==0&&i!=2)continue;//偶数和1排除
sign=true;
for(intj=2;j<i;j++){
if(i%j==0){
sign=false;
break;
}
}
if(sign){
num++;
/*System.out.println(""+i);*/
}
}
System.out.println(n+"以内的素数有"+num+"个");
longend=System.currentTimeMillis();
System.out.println("Thetimecostis"+(end-start));
System.out.println("");
}

第二种：主要考虑2 ~ i/2之间的数 ，效率比第一种提高一半

publicvoidtest2(intn){
longstart=System.currentTimeMillis();//取开始时间
intnum=0;
intj;
booleansgin;
for(inti=2;i<=n;i++){

if(i%2==0&&i!=2)continue;//偶数和1排除

sgin=true;
for(j=2;j<=i/2;j++){
if(i%j==0){
sgin=false;
break;
}
}

//打印
if(sgin){
num++;
/*System.out.println(""+i);*/
}
}
System.out.println(n+"以内的素数有"+num+"个");
longend=System.currentTimeMillis();
System.out.println("Thetimecostis"+(end-start));
System.out.println("");
}

第三种：使用开方去过滤Math.sqrt(i)

publicvoidtest3(intn){
longstart=System.currentTimeMillis();//取开始时间
intnum=0;
intj;
booleansgin;
for(inti=2;i<=n;i++){
if(i%2==0&&i!=2)continue;//偶数和1排除

sgin=true;
for(j=2;j<=Math.sqrt(i);j++){
if(i%j==0){
sgin=false;
break;
}
}

//打印
if(sgin){
num++;
/*System.out.println(""+i);*/
}
}
System.out.println(n+"以内的素数有"+num+"个");
longend=System.currentTimeMillis();
System.out.println("Thetimecostis"+(end-start));
System.out.println("");
}

第四种：逆向思维筛选质素，最为高效

publicvoidtest4(intn){
longstart=System.currentTimeMillis();//取开始时间
//素数总和
intsum=0;
//1000万以内的所有素数
//用数组将1000万以内的数分为两大派系，素数用0代替数值，合数用1代替数值；
//一开始默认全部为素数，所以值全部为0，等到开始筛选的时候再把为合数的赋值为1
intnum[]=newint[n];
num[0]=1;//由于1规定不是素数，所以要提前用1标值
//根据埃氏筛法的结论，要得到自然数N以内的全部素数，必须把不大于"二次根号N"的所有素数的倍数剔除，剩下的就是素数
doubleprescription=Math.sqrt(n);
for(inti=2;i<=prescription;i++){
//开始把所有素数的倍数剔除，剩下的就是素数
for(intj=i*i;j<=n;j+=i){
//从i*i开始去除，因为比i*i小的倍数，已经在前面去除过了
//例如：i=5
//5的2倍（10），3倍（15），在i=2的时候，已经去除过了

num[j-1]=1;//把素数的倍数剔除，也就是赋值为1，不是素数就是合数
}
}
//遍历数组，把值为0的数全部统计出来，得到素数之和
for(inti=0;i<num.length;i++){
if(num[i]==0)
sum++;
}
System.out.println(n+"以内的素数有"+sum+"个");
longend=System.currentTimeMillis();
System.out.println("Thetimecostis"+(end-start));
System.out.println("");
}