提问者:小点点

如何使用筛子打印10^8之前的素数?


我最近学习了筛子算法,并开始玩它来学习如何在问题中使用算法。 我正确地编写了代码,因为我在其中找不到任何bug,但是它关闭时没有显示任何输出。 找不到哪里出了问题。 如能提供帮助,将不胜感激。

#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;
}

共1个答案

匿名用户

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

相反,使用向量来存储堆上的数据,如下所示:

vector<bool> isPrime(MAX+1);

这是一个演示。

另外,请注意,您有一个off by one错误,因为您在索引max处进行索引,所以向量的大小应该是max+1

另外,您应该避免使用名称空间std;,以及ll这样的typedef,它们使代码更难阅读。