c++ - 通过Eratosthenes算法的Sieve查找素数(C++)

我想创建一个函数，该函数基于（Sieve of Eratosthenes）算法查找直到数字num的所有素数

这是我的代码：

vector<int> prime(double num){

    vector<int> check;
    vector<int> prime;
    if(num < 2) throw "Number must be bigger than or equal to 2!";
    for(int i = 0; i<num;++i){
        check.push_back(1);
    }
    for(double i = 2;i<sqrt(num);++i){
        int k = 1;
        if(check.at(i) == true){
            for(double j = pow(i,2); j<num; j = j+k*i){
                check[j] = 0;
                prime.push_back(j);
                ++k;
            }
        }
    }
    return prime;
}


int main(){
    int num;
    vector<int> v;
    cout << "Enter number n bigger than 1:";
    cin >> num;
    v = prime(num);
    for(int i;i<v.size();++i){
        cout << v[i];
    }
}

我按部分检查了代码，除此部分外，其他所有工作均正常进行：

for(double i = 2;i<sqrt(num);++i){
    int k = 1;
    if(check.at(i) == true){
        for(double j = pow(i,2); j<num; j = j+k*i){
            check[j] = 0;
            prime.push_back(j);
            ++k;
        }
    }
}

代码中没有错误，但是没有输出，我无法理解为什么。

最佳答案

最里面的循环for(double j = pow(i,2); j<num; j = j+k*i)很可疑。

您只希望在每次迭代中将j增加i，但是您将其增加i的若干倍。

您也不应该将所有j添加到prime中，因为它们都是通过组合构造而成的。而是添加i。

因为for循环会在运行前检查条件，所以您不需要throw表示num
而不是在double中进行整数运算，您可以始终使用int。

vector<int> prime(int num){
    vector<bool> check(num, true); // num copies of true
    vector<int> prime;
    for(int i = 2; i < num; ++i){
        if(check[i]){
            prime.push_back(i);
            for(int j = i*i; j < num; j += i){
                check[j] = false;
            }
        }
    }
    return prime;
}


int main(){
    cout << "Enter number n bigger than 1:";
    int num;
    cin >> num;
    vector<int> v = prime(num);
    for(int i : v){
        cout << i;
    }
}

关于c++ - 通过Eratosthenes算法的Sieve查找素数(C++)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47219483/