爲什麼我的代碼說109不是素數？

Question

我試圖產生素數，我幾乎有它的工作，但由於某種原因，它表明，109是不是素數時，109是素數。

所以，當我輸出我factorCount顯示「113 :: 29」時，113是第30屆首要因素，併爲它的107，而不是109

#include <iostream> 

using namespace std; 

void mark(bool arr[], int a, int n){ 
    int i = 2; 
    int num = 0; 

    while((num = i*a) <= n){ 
     arr[num-1] = 1; 
     i++; 
    } 
} 

void sieve(int n){ 

    int primeCount = 0; 

    if(n >= 2){ 
     bool arr[n]; 

     for(int i=1; i<n; i++){ 
      if(arr[i] == 0){ 
       primeCount++; 
       cout << i+1 << " :: " << primeCount << endl; 

       mark(arr, i+1, n); 
      } 
     } 
    } 
} 

int main(){ 

    int n = 120; 

    sieve(n); 

    return 0; 
} 

Answer 1

代碼使用未初始化的變量：

bool arr[n]; 

for(int i=1; i<n; i++){ 
    if(arr[i] == 0){  // <--- here 

當您沒有將其設置爲任何值時，檢查arr[i]的值。

另外，bool arr[n];在C++中是非法的，儘管一些編譯器將它作爲擴展名添加它。在標準C++中，編譯時必須知道數組邊界。要修復它，改變bool arr[n];到：

std::vector<unsigned char> arr(n); // note: parentheses, not square brackets 

這個版本將零初始化成員。不幸的是vector<bool>不會在這裏工作，因爲這有一個奇怪的專業化。您需要通過&arr[0]至mark，而不僅僅是arr。