c - Eratosthenes 停止筛

Question

我正在尝试通过维基百科页面实现埃拉托色尼筛法，但出于某种原因，这段代码停止并且没有完成。我是 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 方法不起作用。你将不得不交回从你的例程中找到的素数的数量。