核心思想：用”排除法”找质数

质数：只能被1和自己整除的数（如2,3,5,7,11…）

合数：能被其他数整除的数（如4,6,8,9,10…）

关键发现：所有合数都是某个质数的倍数！

• 比如：4=2×2, 6=2×3, 8=2×4, 9=3×3, 10=2×5…

所以，如果我们找到所有质数，然后把它们的倍数都去掉，剩下的就是质数。

具体操作步骤（以找1-30的质数为例）

第1步：准备数字列表

写下数字2到30（1不是质数）：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

第2步：从最小的数字2开始

• 2是质数（保留）
• 划掉2的所有倍数：4,6,8,10,12,14,16,18,20,22,24,26,28,30

2 3 4̶ 5 6̶ 7 8̶ 9 1̶0̶ 11 1̶2̶ 13 1̶4̶ 15 1̶6̶ 17 1̶8̶ 19 2̶0̶ 21 2̶2̶ 23 2̶4̶ 25 2̶6̶ 27 2̶8̶ 29 3̶0̶

第3步：找下一个没被划掉的数3

• 3是质数（保留）
• 划掉3的所有倍数：9,15,21,27

2 3 4̶ 5 6̶ 7 8̶ 9̶ 1̶0̶ 11 1̶2̶ 13 1̶4̶ 1̶5̶ 1̶6̶ 17 1̶8̶ 19 2̶0̶ 2̶1̶ 2̶2̶ 23 2̶4̶ 25 2̶6̶ 2̶7̶ 2̶8̶ 29 3̶0̶

第4步：找下一个没被划掉的数5

• 5是质数（保留）
• 划掉5的所有倍数：25

2 3 4̶ 5 6̶ 7 8̶ 9̶ 1̶0̶ 11 1̶2̶ 13 1̶4̶ 1̶5̶ 1̶6̶ 17 1̶8̶ 19 2̶0̶ 2̶1̶ 2̶2̶ 23 2̶4̶ 2̶5̶ 2̶6̶ 2̶7̶ 2̶8̶ 29 3̶0̶

第5步：找下一个没被划掉的数7

• 7是质数（保留）
• 7×7=49 > 30，没有需要划掉的数了

最终剩下的质数：2,3,5,7,11,13,17,19,23,29

代码实现（通俗版）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    if (n < 2) {
        cout << 0;  // 小于2没有质数
        return 0;
    }
    
    // 创建一个数组记录每个数是不是质数
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = false;  // 0不是质数
    isPrime[1] = false;  // 1不是质数
    
    // 开始筛选
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {  // 如果i是质数
            // 划掉i的倍数（从i×i开始，因为更小的倍数已经被划掉了）
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 统计质数个数
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }
    
    cout << count;
    return 0;
}

重要说明

1. 为什么从i×i开始划掉？
   • 比如i=5时，5×2=10已经被2划掉了，5×3=15已经被3划掉了
   • 所以直接从5×5=25开始划掉，避免重复工作
2. 为什么到√n就够了？
   • 如果n=100，√100=10
   • 任何大于10的合数，比如77=7×11，已经被7或11划掉了
3. 为什么用vector<bool>？
   • 它可以记录每个数字是不是质数
   • 比逐个检查每个数快得多