當我要素數時，爲什麼我的程序會給我所有的非素數？

我想使用位數組和Eratosthenes的Sieve算法來查找一定範圍內的所有素數。我的代碼編譯，但它打印所有非素數，而不是素數（2除外，因爲我要求我的Sieve函數打印2）。有人可以查看我的代碼，並給我一些關於如何解決它的提示嗎？非常感謝您的幫助。謝謝！當我要素數時，爲什麼我的程序會給我所有的非素數？

注：我的作業要求是使用位陣列。

#include <stdio.h> 
#include <stdlib.h> 

//#define MAXBYTES 1000000 
#define MAXBYTES 10 


void setBit(unsigned int A[], int k); 
unsigned getBit(unsigned int A[], int k); 
void print_prime (int prime_num); 
void sieve_Prime(unsigned int bit_arr[]); 

int main (int argc, char** argv) 
{ 
    //int bit_arr[MAXBYTES];  //This is the bit array (32 X MAXBYTES) 
    unsigned int bit_arr[MAXBYTES];  //or bit_arr[MAXBYTES] 
    int i; 

    for (i=0; i < MAXBYTES; i++) 
    { 
     bit_arr[i] = 0x00;   //initialize all bits to 0s 
    } 

    setBit(bit_arr, 0);    //0 is not prime, set it to be 1 
    setBit(bit_arr, 1);    //1 is not prime, set it to be 1 

    sieve_Prime(bit_arr); 
    printf("\n"); 

    return 0; 

} 

//Set the bit at the k-th position to 1 
void setBit(unsigned int A[], int k) 
{ 
    int i = k/32; 
    int pos = k % 32; 

    unsigned int flag = 1;  //flag = 0000 ..... 00001 
    flag = flag << pos;   //flag = 0000...010...000 (shifted k positions) 

    A[i] = A[i] | flag;   //Set the bit at the k-th position in A[i]; 
} 

//get the bit at the k-th position 
unsigned getBit(unsigned int A[], int k) 
{ 
    int i =k/32; 
    int pos = k % 32; 

    unsigned int flag = 1; 

    flag = flag << pos; 

    if (A[i] & flag) 
     return 1; 
    else 
     return 0; 
} 


void print_prime (int prime_num) 
{ 
    //print a prime number in next of 8 columns 
    static int numfound=0; 

    if (numfound % 8 == 0) 
     printf("\n"); 
    if (prime_num+1 < MAXBYTES*8) 
     printf("%d\t", prime_num); 
    numfound++; 
} 

void sieve_Prime(unsigned int bit_arr[]) 
{ 
    int i; 
    int k; 
    int next_prime = 2; 

    print_prime(2); 

    while (next_prime+1 < MAXBYTES*8) 
    { 
     k = next_prime; 

     //multiples of next_prime is not primpe 
     while(next_prime*k < MAXBYTES*8) 
     { 
      setBit(bit_arr, next_prime*k);  //set it to be 1 
      k++;  
     } 

     //find next_prime by skipping non-prime bits marked 1 
     while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, ++next_prime)) 
     { 
      print_prime(next_prime); 
     } 
    } 
}

來源

2013-08-17 user2203774

的問題是你的循環：

while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, ++next_prime)) 
{ 
    print_prime(next_prime); 
}

你保持承印物而位爲（即當你知道這是不是一個素數）。因此，基本上，您的循環是「在打印下一個素數時打印所有數字」，而不是「在循環中查找下一個素數，然後打印下一個素數」。

我懷疑你想要的東西，如：

next_prime++; // We always want to at least move on once... 
while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, next_prime)) 
{ 
    next_prime++; 
} 
print_prime(next_prime);

我沒有檢查這是否是所有這是錯誤的代碼，但它肯定是固定的初始的事情。

來源

2013-08-17 18:02:22

謝謝你的提示。我嘗試了你的建議，但沒有奏效。我得到了一堆2。還有其他建議嗎？ – user2203774

@ user2203774：那麼你有沒有嘗試通過這個調試？你需要學會診斷問題。你很可能需要一個無條件的'next_prime ++;'在循環之前 - 將它編輯到我的答案中。 –

謝謝。我對編程非常陌生。我想了解更多關於調試的信息。我會仔細看看的。 – user2203774

您可以簡單地通過添加下一個初始化構建初始化爲零值的陣列：

unsigned int bit_arr[MAXBYTES] = { };

然後，陣列的每個成員將持有零值。另外，儘量避免諸如printf("\n");之類的事情。如果您只需要一次輸出一個符號，則最好使用putchar('\n')。

此外，如果不在此翻譯單元之外使用此例程，則可以將static關鍵字添加到您的工作函數原型和定義中，但main函數除外。

來源

2013-08-17 18:17:06 mesmerizingr

當我要素數時，爲什麼我的程序會給我所有的非素數？

回答

相關問題