在实现代码之前，我们要明确什么是素数？
所谓素数就是质数，只能被1和它本身整除的数字
1、普通实现的方法
如果要判断i是否为素数的话？
拿2~i-1的数字去试除i
1.如果i被整除，就说明i不是素数
2.如果2~i-1之间的数字都不能整除i,说明i是素数
#include<stdio.h> int main() { int i = 0; for (i = 100; i <= 200; i++) { int flag = 1;//假设i为素数 //判断i是否为素数 int j = 0; for (j = 2; j < i; j++) { if (i % j == 0) { flag = 0;//i不是素数 break; } } if (flag == 1) printf("%d ", i); } return 0; }
2、优化后的方法
假设m=a*b,且a和b都不等于1，那么a和b中至少有一个小于等于开平方m
假设a<b,那么如果我们能在2~sqrt(m) 中肯定能找到a,那么再查找b就有些多于了。
同时偶数必定不是素数
#include<stdio.h> #include<math.h> int main() { int i = 0; for (i = 101; i <= 200; i+=2) { int flag = 1;//假设i为素数 //判断i是否为素数 int j = 0; for (j = 2; j <=sqrt(i); j++) { if (i % j == 0) { flag = 0;//i不是素数 break; } } if (flag == 1) printf("%d ", i); } return 0; }
