求10000以内所有的质数

首先，要清楚质数（素数）的概念。质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

其次根据质数的定义，我们可以总结以下几种算法去计算10000以内所有的质数：

算法一：判断该数i去能否被2到i的1/2之间任意的数整除，能--->不是质数；不能--->是质数

public static void main(String[] args) { //算法一：判断该数i去能否被2到i的1/2之间任意的数整除，能--->不是质数；不能--->是质数 final int NUM = 10000; int count = 0;//计循环次数 for (int i = 2; i <= NUM; i++ ,count++){ boolean isPrime = true;//true--->是质数 false---->不是质数 //判断该数i去能否被2到i的1/2之间任意的数整除，能--->不是质数；不能--->是质数 for (int j = 2; j < i/2; j++ ,count++){ if (i % j == 0){ isPrime = false; break; } } if (isPrime){ System.out.println(i); } } System.out.println("一共循环了"+count+"次"); }

结果：

一共循环了次

算法二：判断该数i去能否被2到i的算术平方根之间任意的数整除，能--->不是质数；不能--->是质数

public static void main(String[] args) { //算法二：判断该数i去能否被2到i的算术平方根之间任意的数整除，能--->不是质数；不能--->是质数 final int NUM = 10000; int count = 0;//计循环次数 for (int i = 2; i <= NUM; i++ ,count++){ boolean isPrime = true;//true--->是质数 false---->不是质数 //判断该数i去能否被2到i的算术平方根之间任意的数整除，能--->不是质数；不能--->是质数 for (int j = 2; j <= Math.sqrt(i); j++ ,count++){ if (i % j == 0){ isPrime = false; break; } } if (isPrime){ System.out.println(i); } } System.out.println("一共循环了"+count+"次"); }

结果：

一共循环了次

算法三：判断该数i是奇数并且去能否被2到i的算术平方根之间任意的奇数整除（包含2，不包括其他偶数），能--->不是质数；不能--->是质数

public static void main(String[] args) { //算法三：判断该数i是奇数并且去能否被2到i的算术平方根之间任意的奇数整除（包含2，不包括其他偶数），能--->不是质数；不能--->是质数 final int NUM = 10000; int count = 0;//计循环次数 for (int i = 2; i <= NUM; i = i==2 ? i+1: i+2,count++){ boolean isPrime = true;//true--->是质数 false---->不是质数 //判断该数i是奇数并且去能否被2到i的算术平方根之间任意的奇数整除（包含2，不包括其他偶数），能--->不是质数；不能--->是质数 for (int j = 2; j <= Math.sqrt(i); j = j==2 ? j+1: j+2 ,count++){ if (i % j == 0){ isPrime = false; break; } } if (isPrime){ System.out.println(i); } } System.out.println("一共循环了"+count+"次"); }

结果：

一共循环了62185次

算法四：判断该数i是否能被小于其开平方根的质数整除并且为奇数，是--->是质数；不是--->不是质数

public static void main(String[] args) { //算法四：判断该数i是否能被小于其开平方根的质数整除并且为奇数，是--->是质数；不是--->不是质数 final int NUM = 10000; //定义数组array 来储存质数 int[] array = new int[NUM/2]; int size = 0,count = 0; //将质数2赋值给array[0] array[size++] = 2; System.out.println("2"); for (int i = 3; i<=NUM;i += 2,count++){ boolean is = true;// true--->质数 false--->不是质数 //判断该数i是否能被小于其开平方根的质数整除并且为奇数，是--->是质数；不是--->不是质数 for (int j = 0; array[j]<=(int)Math.sqrt(i); j++,count++){ if (i%array[j] == 0){ is = false; break; } } if (is){ array[size++] = i; System.out.println(i); } } System.out.println("循环了"+count+"次"); }

结果：

循环了39982次

通过上述四种算法，我们可以明显的发现，第四种算法（判断该数i是否能被小于其开平方根的质数整除并且为奇数，是--->是质数；不是--->不是质数）循环的次数最少，系统的效率最高，但其也有相比其他算法的不足：占用系统空间比较大。我们优先选择第四种的算法。

今天的文章求10000以内所有的质数分享到此就结束了，感谢您的阅读。

求10000以内所有的质数

相关推荐