Java求质数的五种方法！

2023-09-03 21:10| 来源: 网络整理| 查看: 265

Java求质数的五种方法五种方法第一种第二种第三种第四种第五种结果：总结

五种方法

java求质数的五种方法，使用某种看你喜好！

提示：以下是本篇文章正文内容，下面案例可供参考

第一种

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

代码如下（示例）：

public static void test1(int n){ long start = System.currentTimeMillis(); //取开始时间 int num=0; boolean sign; for(int i=2;i if(i%j==0){ sign=false; break; } } if (sign){ num++; //System.out.println(""+i); } } System.out.println(n+"以内的素数有"+num+"个"); long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); } 第二种

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

代码如下（示例）：

public static void test1(int n){ long start = System.currentTimeMillis(); //取开始时间 int num=0; int j; boolean sgin; for (int i = 2; i if (i % j == 0) { sgin= false; break; } } //打印 if (sgin) { num++; //System.out.println(""+i); } } System.out.println(n+"以内的素数有"+num+"个"); long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); } 第三种

使用开方去过滤 Math.sqrt(i)

代码如下（示例）：

public static void test4(int n){ long start = System.currentTimeMillis(); //取开始时间 int num=0; int j; boolean sgin; for (int i = 2; i if (i % j == 0) { sgin = false; break; } } //打印 if (sgin) { num++; /* System.out.println(""+i);*/ } } System.out.println(n+"以内的素数有"+num+"个"); long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); } 第四种

逆向思维筛选质素，效率很高

代码如下（示例）：

public static void test5(int n){ long start = System.currentTimeMillis(); //取开始时间 //素数总和 int sum = 0; //1000万以内的所有素数 //用数组将1000万以内的数分为两大派系，素数用0代替数值，合数用1代替数值； //一开始默认全部为素数，所以值全部为0，等到开始筛选的时候再把为合数的赋值为1 int num[] = new int[n]; num[0] = 1; //由于1规定不是素数，所以要提前用1标值 //根据埃氏筛法的结论，要得到自然数 N 以内的全部素数，必须把不大于" 二次根号 N "的所有素数的倍数剔除，剩下的就是素数 double prescription = Math.sqrt(n); for (int i = 2; i //从i*i开始去除，因为比i*i小的倍数，已经在前面去除过了 //例如：i=5 //5的2倍（10），3倍（15），在i=2的时候，已经去除过了 num[j-1] = 1; //把素数的倍数剔除，也就是赋值为1，不是素数就是合数 } } //遍历数组，把值为0的数全部统计出来，得到素数之和 for (int i = 0; i long start = System.currentTimeMillis(); //取开始时间 for (int i = 1;i }else{ //System.out.print(i + " "); } } long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); } 结果：

test1(100000); System.out.println("-------------------"); test2(100000); System.out.println("--------------------"); test3(100000); System.out.println("--------------------"); test4(100000); System.out.println("--------------------"); test5(100000);

100000以内的素数有9592个 The time cost is 2659

------------------- 100000以内的素数有9592个 The time cost is 913

-------------------- 100000以内的素数有9592个 The time cost is 17

-------------------- The time cost is 6

-------------------- The time cost is 5

总结

提示：这里对文章进行总结：

备注：感谢前辈们提供的学习资源，前四种来自：java求质数的四种方法！如有冒犯，请多多谅解！！！感谢观看！！！

【本文地址】

公司简介

联系我们