c++ - Eratosthenes C++算法的筛法

Question

我正在尝试实现这个算法，但我很难找到该算法来查找最大 1000 的素数。我不太明白，但我的代码没有给我正确的输出，如果您可以建议我更改代码的方法，我将不胜感激。

#include <iostream>

using namespace std;

bool isPrime(int n);

int main() {
  int i;
  for(i = 1; i <= 1000; i++){
    if( isPrime(i)) cout << "This number " << i <<  " is a prime. " << endl;
  }
}

bool isPrime(int n){
  if(n <= 1){
    return false;
  }
  if(n == 2){
    return true;
  }
  for(int i = 2; i < n; i++){
    if(n % i == 0){
        return false;   
    }else{
        return true;
    }
  }
}

Answer 1

您在 isPrime() 内的 for 循环内做出的决定是错误的。这是终止循环的标准:

if(n % i == 0){

但是 else 部分不是终止的理由。您必须等到 for 循环结束。像这样:

for(int i = 2; i < n; i++){
    if(n % i == 0){
        // Here, we are sure that n can be divided by any other numbers than 1 and n.
        return false;   
    }
}

// Here, we are sure that n cannot be divided by any number 2 .. (n-1).
return true;
}  

顺便说一下，你只需要检查直到 n 的平方根。您可以节省其余部分。