分割故障（核心轉儲）與篩算法

我一直在嘗試使用下面的代碼來實現篩算法：分割故障（核心轉儲）與篩算法

#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故障？爲什麼？

來源

2014-10-20 AbdElHameed

_「什麼可能導致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:14:00 AbdElHameed

'<= theLimit'對我仍然看起來很可疑。這不應該是'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++; 
       } 
}

這是從我的一個代碼中取得的。我認爲它會幫助你。 :)

來源

2014-10-20 18:17:14

分割故障（核心轉儲）與篩算法

回答

相關問題