c - 我想优化这个程序

Question

我最近开始学习 c，作为编程练习，我编写了一个程序，用于计算并列出从 0 到用户输入的最大值的素数。这是一个相当短的程序，所以我将在此处发布源代码。

// playground.c
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main ()
{
    int max;
    printf("Please enter the maximum number up to which you would like to see all primes listed: "
      );   scanf("%i", &max);

    printf("All prime numbers in the range 0 to %i:\nPrime number: 2\n", max);


    bool isComposite;
    int primesSoFar[(max >> 1) + 1];
    primesSoFar[0] = 2;
    int nextIdx = 1;

    for (int i = 2; i <= max; i++)
    {
        isComposite = false;
        for (int k = 2; k <= (int)sqrt(i) + 1; k++)
        {
            if (k - 2 < nextIdx)
            {
                if (i % primesSoFar[k - 2] == 0)
                {
                    isComposite = true;
                    k = primesSoFar[k - 2];
                }
            }else
            {
                if (i % k == 0) isComposite = true;
            }

        }
        if (!isComposite)
        {
            printf("Prime number: %i\n", i);
            primesSoFar[nextIdx] = i;
            nextIdx++;

        }

    }

    double primeRatio = (double)(nextIdx + 1) / (double)(max);
    printf("The ratio of prime numbers to composites in range 0 to %d is %lf", max, primeRatio);

    return 0;
}

我对优化这个程序产生了奇怪的兴趣，但我遇到了困难。数组 primesSoFar 是根据计算出的最大大小进行分配的，理想情况下该大小不大于从 0 到 max 的素数数量。哪怕再大一点也好；只要不是更小。有没有一种方法可以计算数组所需的大小，而不依赖于首先计算最大素数？

我已经更新了代码，应用了建议的优化，并在看起来有用的地方添加了内部文档。

// can compute all the primes up to 0x3FE977 (4_188_535). Largest prime 4_188_533

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main ()
{
    int max;
    printf("Please enter the maximum number up to which you would like to see all primes listed: "
      );   scanf("%i", &max);

    // The algorithm proper doesn't print 2.
    printf("All prime numbers in the range 0 to %i:\nPrime number: 2\n", max);


    bool isComposite;
    // primesSoFar is a memory hog. It'd be nice to reduce its size in proportion to max. The frequency
    // of primes diminishes at higher numerical ranges. A formula for calculating the number of primes for
    // a given numerical range would be nice. Sadly, it's not linear.
    int PRIMES_MAX_SIZE = (max >> 1) + 1;
    int primesSoFar[PRIMES_MAX_SIZE];
    primesSoFar[0] = 2;
    int nextIdx = 1;
    int startConsecCount = 0;

    for (int i = 2; i <= max; i++)
    {
        isComposite = false; // Assume the current number isn't composite.
        for (int k = 2; k <= (int)sqrt(i) + 1; k++)
        {
            if (k - 2 < nextIdx) // Check it against all primes found so far.
            {
                if (i % primesSoFar[k - 2] == 0)
                {
                    // If i is divisible by a previous prime number, break.
                    isComposite = true;
                    break;
                }else
                {
                    // Prepare to start counting consecutive integers at the largest prime + 1. if i 
                    // isn't divisible by any of the primes found so far.
                    startConsecCount = primesSoFar[k - 2] + 1;
                }
            }else
            {
                if (startConsecCount != 0) // Begin counting consecutively at the largest prime + 1.
                {
                    k = startConsecCount;
                    startConsecCount = 0;
                }

                if (i % k == 0)
                {
                    // If i is divisible by some value of k, break.
                    isComposite = true;
                    break;
                }
            }

        }
        if (!isComposite)
        {
            printf("Prime number: %i\n", i);

            if (nextIdx < PRIMES_MAX_SIZE)
            {
                // If the memory allocated for the array is sufficient to store an additional prime, do so.
                primesSoFar[nextIdx] = i;
                nextIdx++;
            }

        }

    }

    // I'm using this to get data with which I can find a way to compute a smaller size for primesSoFar.
    double primeRatio = (double)(nextIdx + 1) / (double)(max);
    printf("The ratio of prime numbers to composites in range 0 to %d is %lf\n", max, primeRatio);

    return 0;
}

编辑: primesSoFar 应该是 0 到最大值范围大小的一半。毫无疑问，这引起了一些困惑。

Answer 1

我可以给你两个主要想法，因为我曾参与过一个讨论这个问题的项目。

1. 大于 3 的素数要么是 6k-1 要么是 6k+1，例如 183 就不可能是素数，因为 183=6x30+ 3，所以你甚至不必检查它。 (注意，这个条件是必要条件，但不是充分条件，例如 25 是 6x4+1 但不是素数)
2. 如果一个数不能被任何小于或等于其根的素数整除，则该数是素数，因此最好从已找到的较小素数中受益。

因此，您可以从包含 2 和 3 的 primesList 开始，然后迭代 k 来测试所有6k-1 和 6k+1 数字(5、7、11、13、17、19、23、25...)使用我给您的第二条规则，通过对 primesList 中小于或等于您正在检查的数字的根的元素进行除法，如果您发现只有一个元素除以它，您只需停止并传递给另一个元素，因为这个元素不是质数，否则(如果没有人能整除它):通过添加这个新质数来更新 primesList。