Eratosthenes的篩子停止

Question

我試圖通過維基百科頁面實現Eratosthenes的篩子，由於某些原因，此代碼停止並未完成。我是C的初學者，所以請解釋一下我是否濫用了任何東西。

我不確定，但是我濫用sizeof(primes)/sizeof(int)？

#include <stdio.h> 
#include <malloc.h> 

#define bool char 
#define false 0 
#define true 1 

void sieveOfEratosthenes(const int until, int* primes); 

int main(int argc, char** argv) { 
    puts("sieveOfEratosthenes: 120"); 
    int* primes = malloc(sizeof(int)); 
    sieveOfEratosthenes(120, primes); 
    for (int i = 0; i < sizeof(primes)/sizeof(int); i++) { 
     printf("%d:%d\n", i, primes[i]); 
    } 
} 

void sieveOfEratosthenes(const int until, int* primes) { 
    int numbers[until]; 
    for (int p = 2; p < until; p++) { 
     numbers[p] = true; 
    } 

    int p = 2; 
    while (true) { 
     for (p = p * p; p < until; p += p) { 
      numbers[p] = false; 
     } 
     for (int count = p; count < until; count++) { 
      if (numbers[count] == true) { 
       p = count; 
       break; 
      } 
     } 
     if (p == until) { 
      break; 
     } 
    } 
    int j = 0; 
    for (int i = 0; i < until; i++) { 
     if (numbers[i] == true) { 
      primes = realloc(primes, (j + 1) * sizeof(int)); 
      primes[j++] = i; 
     } 
    } 
    return; 
} 

Answer 1

有在你的日常幾個問題：

void sieveOfEratosthenes(const int until, int* primes) { 
    int numbers[until], count; 
    for (int p = 2; p < until; p++) { 
     numbers[p] = true; 
    } 

    int p = 2; 
    while (true) { 
     // You should not overwrite p since you later need it. 
     for (int i = p * p; i < until; i += p) { 
      numbers[i] = false; 
     } 
     for (count = p + 1; count < until; count++) { // p+1 is the next prime candidate 
      if (numbers[count] == true) { 
       p = count; 
       break; 
      } 
     } 
     if (count >= until) { // You break when the loop above finishes 
      break; 
     } 
    } 
    int j = 0; 
    for (int i = 2; i < until; i++) { // 2 is the first prime, not 0 
     if (numbers[i] == true) { 
      primes = realloc(primes, (j + 1) * sizeof(int)); 
      primes[j++] = i; 
     } 
    } 
    return; 
} 

除此之外，該sizeof primes方法是行不通的。你將不得不從你的例程中回收找到的素數。