5.4 素数问题

“小朋友们，我们来聊一聊数学中一个非常重要的概念——素数，”我认真地说，”素数是只能被1和自身整除的数，比如2、3、5、7等。今天我们将学习如何判断一个数是否为素数。”

5.4.1 素数问题

题目描述： 编一个程序，计算 1∼n 范围内素数的个数。

输入格式： 包括多组数据（不超过 100 组），每组数据仅有一个整数 n（1≤n≤100），输入以 0 结束。

输出格式： 对于每组数据输入，输出一行，为 1∼n（包括 n）之间的素数的个数。

样例输入：

1
10
65
100
0

样例输出：

0
4
18
25

代码实现：

int a[110];              // 定义数组存储输入的数
int i = 0;               // 初始化索引
while(1){                // 无限循环读入数据
    cin >> a[++i];       // 读入一个数
    if(a[i] == 0) break; // 如果输入为0则退出循环
}
for(int i = 1; a[i] != 0; i++){
    int cnt = 0;         // 初始化素数计数器
    for(int j = 2; j <= a[i]; j++){
        bool isPrime = true;  // 假设j是素数
        for(int k = 2; k * k <= j; k++){  // 只需检查到j的平方根
            if(j % k == 0){   // 如果j能被k整除
                isPrime = false;  // j不是素数
                break;        // 退出循环
            }
        }
        if(isPrime == true) cnt++;  // 如果j是素数，计数器加1
    }
    cout << cnt << endl;  // 输出素数个数
}

算法解析：

1. 循环读入数据，直到遇到0停止
2. 对于每个输入的数n，计算1~n范围内素数的个数
3. 判断一个数j是否为素数的方法是：
   • 从2到√j遍历所有可能的因子k
   • 如果j能被任何k整除，则j不是素数
   • 否则j是素数
4. 最后输出范围内素数的个数