判断素数

算法要求算法思路编译环境方法一方法二方法三方法四 总体代码

算法要求

实现一个函数，判断一个数是不是素数。 利用上面实现的函数打印100到200之间的素数。

算法思路

首先了解概念：素数是什么？ 素数：即质数，除了1和自己之外，再没有其他的约数，则该数据为素数。通俗讲就是一个数只能被1和它自身所整除。例如：十以内的素数：1，2，3，5，7，9。上述数字只能被1和数字本身整除。

编译环境

Win10，VS2015

方法一

最简单直接的办法，挨个试。从1开始逐个遍历到数字本身。代码实现：

int IsPrimeNumber1(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, i)之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j < i; j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j和i相等，说明[2, i）之间的所有数据都不能被i整除，则i为素数 if (j == i) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; }

上述方法的缺陷：超过i一半的数据，肯定不是i的倍数，上述进行了许多没有意义的运算。 举个例子：10的一半是5，就不需要检测大于5的数字，即5~10，因为超过5的数字不可能是10的倍数。6x2=12，7x2=14，这几个数字已经超过10本身了。

方法二

每拿到一个数据，只需要检测其：[2, i/2]区间内是否有元素可以被2i整除即可，可以说明i不是素数

int IsPrimeNumber2(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, i/2]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= i/2; j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j大于i/2，说明[2, i/2]之间的所有数据都不能被i整除，则i为素数 if (j >i/2) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; }

方法二仍然包含了一些重复的数据，再优化：原因可以见方法三。

方法三

如果i能够被[2, sqrt(i)]之间的任意数据整除，则i不是素数 原因：如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于 sqrt(m)。

int IsPrimeNumber3(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, sqrt(i)]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= sqrt(i); j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j大于sqrt(i)，说明[2, sqrt(i)]之间的所有数据都不能被i整除，则i为素数 if (j > sqrt(i)) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; }

方法四

继续对方法三优化，只要i不被[2, sqrt(i)]之间的任何数据整除，则i是素数，但是实际在操作时i不用从101逐渐递增到200，因为除了2和3之外，不会有两个连续相邻的数据同时为素数！ 注意：此方法i从101开始计数

int IsPrimeNumber4(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin+1; i < end; i+=2) { int j = 0; //判断i是否为素数：用[2, sqrt(i)]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= sqrt(i); j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j大于sqrt(i)，说明[2, sqrt(i)]之间的所有数据都不能被i整除，则i为素数 if (j > sqrt(i)) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; }

总体代码

#include <stdio.h> #include <windows.h> #include <math.h> #pragma warning(disable:4996) int IsPrimeNumber1(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, i)之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j < i; j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j和i相等，说明[2, i）之间的所有数据都不能被i整除，则i为素数 if (j == i) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; } int IsPrimeNumber2(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, i/2]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= i/2; j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j和i/2相等，说明[2, i/2]之间的所有数据都不能被i整除，则i为素数 if (j >i/2) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; } int IsPrimeNumber3(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin; i < end; i++) { int j = 0; //判断i是否为素数：用[2, sqrt(i)]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= sqrt(i); j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j大于sqrt(i)，说明[2, sqrt(i)]之间的所有数据都不能被i整除，则i为素数 if (j > sqrt(i)) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; } int IsPrimeNumber4(int begin, int end) { int i = begin; int count = 0; //外层循环用来获取100~200之间的所有数据 for (i = begin+1; i < end; i+=2) { int j = 0; //判断i是否为素数：用[2, sqrt(i)]之间的每个数据去被i除，只要有一个可以被整除，则不是素数 for (j = 2; j <= sqrt(i); j++) { if (i%j == 0) { break; } } // 上述循环结束之后，如果j大于sqrt(i)，说明[2, sqrt(i)]之间的所有数据都不能被i整除，则i为素数 if (j > sqrt(i)) { count++; printf("%d ", i); } } printf("\ncount=%d\n", count); return 1; } int main() { int begin = 100; int end = 200; IsPrimeNumber1(begin,end); IsPrimeNumber2(begin, end); IsPrimeNumber3(begin, end); IsPrimeNumber4(begin, end); system("pause"); return 0; }

运行结果：

>> 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 >> count=21