使用java，求质数的4种方法

布满荆棘的人生 2024-04-01 18:27 55阅读 0赞

![822f86da087553328500c99a2b4b9d18.jpeg][]

的方法：用一个数x去除2至sqrt(x)（即该数的开方），如果能被整除， 则表明此数不是素数，反之是素数。

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

public void test1(int n)\{long start = System.currentTimeMillis(); //取开始时间int num=0;[boolean][] sign;for(int i=2;i<n;i++)\{if(i % 2 == 0 && i != 2 ) continue; //偶数和1排除sign=true;for (int j=2;j<i;j++)\{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 void test2(int n)\{long start = System.currentTimeMillis(); //取开始时间int num=0;int j;boolean sgin;for (int i = 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+"以内的[素数][Link 1]有"+num+"个");long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); \}

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

public void test3(int n)\{long start = System.currentTimeMillis(); //取开始时间int num=0;int j;boolean sgin;for (int i = 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+"个");long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); \}

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

public void test4(int n)\{long start = System.currentTimeMillis(); //取开始时间//素数总和int sum = 0;//1000万以内的所有素数//用数组将1000万以内的数分为两大派系，素数用0代替数值，合数用1代替数值；//一开始默认全部为素数，所以值全部为0，等到开始筛选的时候再把为合数的赋值为1int num\[\] = new int\[n\]; num\[0\] = 1; //由于1规定不是素数，所以要提前用1标值//根据埃氏筛法的结论，要得到自然数 N 以内的全部素数，必须把不大于" 二次根号 N "的所有素数的倍数剔除，剩下的就是素数double prescription = Math.sqrt(n);for (int i = 2; i <= prescription; i++) \{//开始把所有素数的倍数剔除，剩下的就是素数for (int j = 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 (int i = 0; i < num.length; i++) \{if(num\[i\]==0) sum++; \} System.out.println(n+"以内的素数有"+sum+"个");long end = System.currentTimeMillis(); System.out.println("The time cost is " + (end - start)); System.out.println(""); \}

public static void main(String\[\] args) \{ Demo1 demo1 = new Demo1(); demo1.test1(100000); demo1.test2(100000); demo1.test3(100000); demo1.test4(100000); \}

结果：

100000以内的素数有9592个

The time cost is 1558

100000以内的素数有9592个

The time cost is 700

100000以内的素数有9592个

The time cost is 12

100000以内的素数有9592个

The time cost is 4

来源：[https://www.weidianyuedu.com][https_www.weidianyuedu.com]

[822f86da087553328500c99a2b4b9d18.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5f9a4979e485467880341163ec925d0a.jpeg
[boolean]: https://so.csdn.net/so/search?q=boolean&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E7%B4%A0%E6%95%B0&spm=1001.2101.3001.7020
[https_www.weidianyuedu.com]: https://www.weidianyuedu.com