c++ - 使用筛选算法的段错误(核心已转储)

Question

我一直在尝试使用以下代码实现筛选算法:

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

}

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

什么可能导致段错误？为什么？

Answer 1

首先，我想告诉您，为搜索所有素数而运行的 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++;
               }
 }

这只是取 self 的一个代码。我认为这会对你有所帮助。 :)