博客

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;// 不是素数