时间戳

首页 > 解决方案 > 如何使用 Sieve 打印质数直到 10^8？

c++ - 如何使用 Sieve 打印质数直到 10^8？

问题描述

我最近学习了 Sieve 算法并开始使用它来学习如何在问题中使用该算法。我已经正确编写了代码，因为我在其中找不到任何错误，但它关闭而不显示任何输出。找不到问题所在。帮助将不胜感激。

#include <iostream>
#include <vector>
//#define MAX 10000
typedef long long int ll;
using namespace std;
vector <ll> primes;
void sieve(){
    ll MAX = 100000000;
    bool isPrime [MAX];
    for(ll i = 0;i < MAX; ++i)isPrime[i] = true;
    //isPrime[0] = isPrime[1] = false;
    
    for(ll i=3; i*i <= MAX; i += 2){
        if(isPrime[i]){
            for(ll j = i*i; j <= MAX; j += i){
                isPrime[j] = false;
            }
        }
    }
    primes.push_back(2);
    for(ll i = 3; i <= MAX; i += 2){
        if(isPrime[i]){
            primes.push_back(i);
        }
    }
    for(ll i = 0; i <= 10; ++i){
        cout<<primes[i]<<endl;
    }
}
int main(){
    sieve();
    return 0;
}

标签： c++algorithmnumberssieve-of-eratosthenes

解决方案

您正在创建一个 size 的静态数组10^8，该数组存储在堆栈中。这对于堆栈来说太大了，很可能会导致堆栈溢出。

相反，使用vector将数据存储在堆上的 a，如下所示：

vector<bool> isPrime(MAX+1);

这是一个演示。

另外，请注意您有一个错误，因为您在 index 处进行索引MAX，所以向量应该是 size MAX+1。

此外，您应该避免using namespace std;以及 typedef 之类ll的，它们会使代码更难阅读。

推荐阅读