如何不修改listPrime函数仅修改main函数获取1-100的素数列表？

修改后的完整代码 #

#include <iostream>
const int nmax = 100001;
bool isPrime[nmax];
int listPrime(int num){
 for(int i = 2; i<=num;i++){
  isPrime[i] = true;
 }
 for(int i = 2; i<=num/2;i++){
  if(isPrime[i]==true){
   for(int j =i*2;j<=num;j+=i){
    isPrime[j] = false;
   }  
  } 
 }
 for(int i=2;i<=num;i++){
  if(isPrime[i] == true){
   return i;
  }
 }
}

int main (){
    // 调用listPrime初始化素数标记数组
    listPrime(100);
    
    std::cout << "1到100之间的素数列表：" << std::endl;
    // 遍历全局数组，收集所有标记为素数的数
    for(int i = 2; i <= 100; ++i){
        if(isPrime[i]){
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
    
    return 0;
}

原理说明 #

虽然listPrime函数仅返回第一个素数（2），但它内部完整执行了埃拉托斯特尼筛法：

1. 首先将isPrime数组中2到num的元素初始化为true；
2. 接着通过筛法将所有非素数标记为false；
3. 最后才返回第一个素数。

也就是说，调用listPrime(100)后，全局数组isPrime已经准确标记了1到100之间的所有素数。我们只需要遍历该数组，输出所有值为true的下标即可得到完整素数列表。

内容的提问来源于stack exchange，提问作者Parvez Hossain