使用sieve算法分割故障(核心转储)

Question

我一直在尝试使用以下代码实现sieve算法：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector <int> primes; //all the primes found
    int theLimit = 10E5;

    void sieve (vector <int> &primes, int theLimit); //declaring the function
    sieve (primes, theLimit);

    return 0;
}

void sieve (vector <int> &primes, int theLimit) {
    const int SIZE = theLimit + 1;
    bool oddNonPrimes[SIZE]; //the array that tells you that tells you if the number that represents the current index is a non-prime or not

    for (int i = 0; i < theLimit; ++i) //setting all the array indicies to false
        oddNonPrimes[i] = false;

    primes.push_back(2);

    for (int i = 3; i < theLimit; i += 2){ //start searching for primes,we start with the number 3 and check all odd numbers only
        if (!oddNonPrimes[i]){
             int currNum = i;
             primes.push_back(currNum);
             for (int factor = 2; currNum <= theLimit; ++factor){
                currNum *= factor;
                oddNonPrimes[currNum] = true;
                currNum = i;
            }
        }
    }

}

我已经尝试降低大小，以确保我没有使用太多内存，但仍然不起作用。我也尝试搜索答案，但没有找到任何答案。

是什么导致了Seg故障?为什么？

Answer 1

首先，我想告诉大家，通过判断(！oddNonPrimesi)是否为真来搜索所有素数的for循环应该只对sqrt(theLimit)执行，因为这样会降低复杂度。下面是一个筛分方法，我希望你参考一下。

#include<bits/stdc++.h>
using namespace std;

bool *primality=new bool[10000010];
long long int *p = new long long int[1000001];
int main(){
    long long count=0;
    for(long long int i=0; i<10000010; i++)
        primality[i]=true;
    for(int i=2; i<10010; i++)
        if(primality[i])
            for(long long j=i*i; j<10000010; j+=i)
                primality[j]=false;
            for(int i=2; i<10000010; i++)
               if(primality[i]){
                   p[count]=i;
                   count++;
               }
 }

这是从我的一个代码中提取出来的。我想这会对你有帮助。:)

Answer 2

首先，很抱歉浪费了您的时间。

我应该使用：

for (int factor = 2; (currNum * factor) <= theLimit; ++factor)

而不是：

for (int factor = 2; currNum <= theLimit; ++factor)

否则，当currNum很大，然后乘以因子时，它可能会超过限制，因此它会尝试访问超出数组大小的索引。