分割故障（核心转储）与筛算法

问题描述：

#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故障？为什么？

_“什么可能导致Seg故障？为什么？”_您应该调试这个使用调试器来逐步通过。 – 2014-10-20 17:39:54

bool oddNonPrimes [SIZE]不是标准的C++，如果你想最终移植你的代码，你最好去掉那个 – Creris 2014-10-20 17:40:48

在最内层循环中检查“currNum”的值，因为你实际上乘以内循环变量乘以外部循环变量，我非常确定“currNum”在某些点将比“theLimit”更大，从而访问“oddNonPrimes”边界之外。 – user1074069 2014-10-20 17:50:07

答

首先，对不起，浪费你的时间。

我应该用：

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

相反的：

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

否则，当currNum大，再由因子相乘，它可能变得比限制的，因此它会尝试访问超出数组大小的索引。

' 2014-10-20 18:17:52

currNum AbdElHameed 2014-10-20 18:27:44

答

首先，我想告诉查看if（！oddNonPrimes [i]）是否为true的搜索所有素数的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++; 
       } 
}

这是从我的一个代码中取得的。我认为它会帮助你。 :)

分割故障（核心转储）与筛算法

相关推荐