输入正整数n(n大于等于2),求不大于n的全部质数(素数)【其中一种优化算法】
程序员文章站
2022-06-07 10:31:57
...
1, 质数(素数)概念:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。例如:3 只能被1和3整除,5,7,9 这些都是。4,6这些都不是质数(注意2是质数)。
2,基本思想:
(1)首先2肯定是一个质数,先打印出来
(2)使用循环,从3开始到不大于n。优化要点:不要都遍历到,把偶数的给排除,4,6。。。这些都不是质数
(2.1)判断当前这个数是不是质数:
使用循环,做模运算,如果==0 就不是质数 退出。优化要点:只检测到根号下就可以了。
(2.2)当前数是质数,打印出来。
3,代码实现
#include <iostream>
using namespace std;
int main() {
int n=0; //输入的n
cin >> n;
cout << 2 << endl; // 先输出2
for (int i = 3; i < n; i += 2) {//使用循环检测(<=n)的所有数。优化要点:排除大于2 的偶数,减少不必要的运算
int j;
for (j = 3; j < sqrt(i); j++) {// 使用循环。优化要点:只检测到根号下就可以了。
if (i%j ==0)
break;// 不是素数
}
if (j * j > i)//是素数
cout << i << endl;
}
return 0;
}
效果