三个程序，判断一个数是否为素数，运算量依次递减。
简单粗暴
//函数->判断素数bool IsPrime(int num){for (int i = 2; i < num; i++) {if (num % i == 0) return 0;}return 1;}int main(){int n = 1234567;if (IsPrime(n)) {printf("YES\n");} else {printf("NO\n");}return 0;}
方法1的改进：循环到sqrt（n）
方法一是通过暴力循环，依次判断，其实没必要判断到n，而是判断到sqrt（n）即可。因为如果一个数可以分解为两个数的乘积的情况下，则一定是一个数在sqrt（n）的左侧，一个数在sqrt（n）的右侧，或者两数相等，均为sqrt（n）。因此，判断sqrt（n）左侧的数即可，判断其能否被n整除。
代码如下：
//函数->判断素数bool IsPrime(int num){for (int i = 2; i <= sqrt(num); i++) {if (num % i == 0) return 0;}return 1;}int main(){int n = 1234567;if (IsPrime(n)) {printf("YES\n");} else {printf("NO\n");}return 0;}
如果存在素数，则该素数一定在6或6的倍数两侧
如果一个数为素数，则该素数一定在6或6的倍数两侧。这是一个充分不必要条件，即在6或6的倍数的两侧的数未必就是素数。
程序如下：
//函数->判断素数bool IsPrime(int num){if (num == 1)return 0;if (num == 2 || num == 3) //排除两个小素数return 1;if (num % 6 != 1 && num % 6 != 5) //不在6或6的倍数两侧的均不是素数；return 0;for(int i = 5; i <= sqrt(num); i+=6) {if (num % i == 0 || num % (i+2) == 0) {return 0;}}return 1;}int main(){int n = 1234567;if (IsPrime(n)) {printf("YES\n");} else {printf("NO\n");}return 0;}
下面是测试三种函数的运算时间。
代码如下：
//测试程序运行时间#include<stdio.h>#include<stdlib.h>#include<time.h>clock_t TimeStart, TimeEnd;double caltime;#define N 150000// 函数->判断素数bool IsPrime1(int num){for (int i = 2; i < num; i++) {if (num % i == 0) return 0;}return 1;}// 函数->判断素数bool IsPrime2(int num){for (int i = 2; i <= sqrt(num); i++) {if (num % i == 0) return 0;}return 1;}// 函数->判断素数bool IsPrime3(int num){if (num == 2 || num == 3) //排除两个小素数return 1;if (num % 6 != 1 || num % 6 != 5) //不在6或6的倍数两侧的均不是素数；return 0;for(int i = 5; i <= sqrt(num); i+=6) {if (num % i == 0 || num % (i+2) == 0) {return 0;}}return 1;}//函数->判断素数bool IsPrime4(int num){if (num == 2 || num == 3) //排除两个小素数return 1;if (num % 6 != 1 || num % 6 != 5) //不在6或6的倍数两侧的均不是素数；return 0;int temp = (int)sqrt(num);for(int i = 5; i <= temp; i+=6) {if (num % i == 0 || num % (i+2) == 0) {return 0;}}return 1;}int main(){TimeStart = clock();for (int i = 2; i < N; i++) {IsPrime1(i);}TimeEnd = clock();caltime = (double)(TimeEnd - TimeStart)/CLOCKS_PER_SEC;//单位为s，CLOCKS_PER_SEC是计算机1秒钟计算的时钟周期数；printf("%f\n", caltime);TimeStart = clock();for (int i = 2; i < N; i++) {IsPrime2(i);}TimeEnd = clock();caltime = (double)(TimeEnd - TimeStart)/CLOCKS_PER_SEC;//单位为s，CLOCKS_PER_SEC是计算机1秒钟计算的时钟周期数；printf("%f\n", caltime);TimeStart = clock();for (int i = 2; i < N; i++) {IsPrime3(i);}TimeEnd = clock();caltime = (double)(TimeEnd - TimeStart)/CLOCKS_PER_SEC;//单位为s，CLOCKS_PER_SEC是计算机1秒钟计算的时钟周期数；printf("%f\n", caltime);TimeStart = clock();for (int i = 2; i < N; i++) {IsPrime4(i);}TimeEnd = clock();caltime = (double)(TimeEnd - TimeStart)/CLOCKS_PER_SEC;//单位为s，CLOCKS_PER_SEC是计算机1秒钟计算的时钟周期数；printf("%f\n", caltime);return 0;}
运算结果为：
可以看出，方法二的效率远高于方法一，方法三的效率远高于方法二。写第四个函数是想测试如果在先执行sqrt（num），然后赋值给temp，免去后反复的计算sqrt函数。看效率能快多少。实际上效果微乎其微，之后再数据量很大的时候，才比方法三快一点，因此实际编程时不需考虑。
