欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

输入正整数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;
}

效果
输入正整数n(n大于等于2),求不大于n的全部质数(素数)【其中一种优化算法】