c - 超过 500000 用 Eratosthenes 的方法

Question

我有一个我无法解决的问题

我想知道给定极限 x 以下的所有素数。允许我输入 x 并使用 Erastosthenes 的方法计算素数。在屏幕上显示结果并将其保存到文本文件。

计算 x 下面的质数，打印它们并将它们保存到文本文件中，我遇到的唯一问题是 x 不能超过 500000 你们能帮帮我吗？

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

void sieve(long x, int primes[]);

main()
{
    long i;
    long x=500000;
    int v[x];

    printf("give a x\n");
    scanf("%d",&x);

    FILE *fp;

    fp = fopen("primes.txt", "w");
    sieve(x, v);
    for (i=0;i<x;i++)
    {
        if (v[i] == 1)
        {
            printf("\n%d",i);
            fprintf(fp, "%d\n",i);
        }
    }
    fclose(fp);
}

void sieve(long x, int primes[])
{
    int i;
    int j;
    for (i=0;i<x;i++)
    {
        primes[i]=1; // we initialize the sieve list to all 1's (True)
        primes[0]=0,primes[1]=0; // Set the first two numbers (0 and 1) to 0 (False)
    }
    for (i=2;i<sqrt(x);i++) // loop through all the numbers up to the sqrt(n)
    {
        for (j=i*i;j<x;j+=i) // mark off each factor of i by setting it to 0 (False)
        {
            primes[j] = 0;
        }
    }

}

Answer 1

通过声明 char v [500000] 而不是 int v [100000]，您将能够处理四倍多的值。

通过声明 unsigned char v [500000] 并为每个素数仅使用一个位，您可以处理八倍以上的值。这使得代码有点复杂。

通过只筛选奇数，您可以处理两倍的值。由于 2 是唯一的偶素数，因此将它们留在筛子中毫无意义。

由于函数中局部变量的内存通常非常有限，您可以使用静态数组处理更多的值。