[C趣味编程]求1~b，求a~b的所有素数
求1~b，求a~b的所有素数
求1~b的所有素数：在求下一个素数N时，可以使用已经求出的素数，仅仅使用它们去模N。这是因为，如果N是合数，它一定可以除尽某个比N小的素数。
求a~b的所有素数：由于求N时，并没有所有的“比N小的素数”存在，所以无法利用上述的技巧。判断的数使用[2,N的开方]的奇数。
?
2中方法，suShu1()效率是比较快的。（不过，需要在N比较大的情况下。）
?
public class SuShu { public static void main(String[] args) { suShu1(30); System.out.println("\r\n---------------------"); suShu2(5, 30); System.out.println("\r\n---------------------"); suShu1(30000); System.out.println("\r\n---------------------"); suShu2(5, 30000); } /** * 打印[1,b]范围内的所有素数<br> * 思想：<br> * 遍历[1,b]范围的所有的奇数n，对每个n，再判断n是否素数：遍历[2,n开方]的素数(这些素数已求出)，看是否有模为0的。<br> * 该方法不同于suShu2()在于“遍历[2,n开方]的素数(这些素数已求出)”，而不是“遍历[2,n开方]的数”，这是因为：<br> * 如果n是素数，它只有1和n这2个素因子；<br> * 如果n是合数，它必定有1，n和其他素因子，所以“遍历[2,n开方]的素数(这些素数已求出)”即可；<br> */ public static void suShu1(int b) { int count=0;//记录循环次数 int[] suShu = new int[b/2+1]; suShu[0] = 2; int index = 1; for (int n = 3; n <= b; n+=2) { boolean notSuShu = false; //遍历[2,n开方]的素数(这些素数已求出) int i=0; while(suShu[i]!=0 && suShu[i] <= Math.sqrt(n) && !notSuShu){ count++; if (n % suShu[i++] == 0) { notSuShu = true; } } if (!notSuShu) { suShu[index++] = n;//将求出的素数存储起来 System.out.print(n+" "); } } System.out.print("\n循环最内部的执行次数： "+count); } /** * 打印[a,b]范围内的所有素数<br> * 思想：<br> * 遍历[a,b]范围的所有的数n，再判断n是否素数：遍历[2,n开方]的数，看是否有模为0的。<br> * 判断n是否素数的方法是：遍历[2,n开方]的奇数。<br> * why n开方?因为<br> * n = 1 * n<br> * n = 2 * (n/2)<br> * n = 3 * (n/3)<br> * n = 5 * (n/5)<br> * ...<br> * n = n开方 * n开方<br> * ...接下去的就和前面重复了<br> */ public static void suShu2(int a, int b) { int count=0;//记录循环次数 if(a ==1 || a==2){//如果是[1,b]或[2,b]，使用suShu1()比较高效！ suShu1(b); return; } if(a % 2 ==0)a++;//将a变成奇数 for (int n = a; n <= b; n+=2) { boolean notSuShu = false; //遍历[2,n开方]的奇数 if(n % 2 == 0)notSuShu = true; for (int i = 3; i <= Math.sqrt(n) && !notSuShu ; i+=2) { count++; if (n % i == 0) { notSuShu = true; } } if (!notSuShu) System.out.print(n+" "); } System.out.print("\n循环最内部的执行次数： "+count); }}??
?
效果：
?
3 5 7 11 13 17 19 23 29
循环最内部的执行次数： 26
---------------------
5 7 11 13 17 19 23 29
循环最内部的执行次数： 13
---------------------
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71....
循环最内部的执行次数： 151925
---------------------
5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 ....
循环最内部的执行次数： 253648
?