超过 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 是唯一的偶素数，因此将它们留在筛子中毫无意义。

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

Answer 2

我相信您遇到的问题是如果堆栈中的元素超过 500000 个，则分配一个 int 数组。这不是一种有效的方法，使用一个数组，其中元素是数字，值指示它是否为素数。如果你想这样做，至少使用 bool，而不是 int，因为这应该只有 1 个字节，而不是 4 个字节。

还要注意这个

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)
}

您正在重新分配每个循环中的前两个元素。把它从循环中取出来。

Answer 3

您将 x 初始化为 500000，然后创建一个包含 x 个元素的数组，因此它将有 500000 个元素。然后你正在阅读 x。当 x 的值发生变化时，数组不会改变大小 - 它固定为 500000 个元素，即创建数组时 x 的值。你想要这样的东西：

long x=500000;

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

int *v = new int[x];

这解决了您的固定大小数组问题，并且还将它从堆栈中取出并放入堆中，这将允许您分配更多 space。它应该达到您可用内存的限制。

Answer 4

将v分配为int的数组是一种浪费，将其作为本地数组是有风险的，堆栈space是有限的。如果数组变得足够大以超过可用堆栈 space，程序将调用未定义的行为并可能崩溃。

虽然有一些方法可以通过将筛阵列更改为仅包含奇数或更少数字的位阵列来提高筛的效率（6n-1 和 6n+1 是一个好技巧），您仍然可以通过简单的更改将简单方法的效率提高 10 倍：

修复primes[0]和primes[1]在循环外，
清除prime的偶数偏移，除了第一个也是唯一一个扫描奇数，
外循环限制使用整数运算，
忽略已知的合数，
只勾选i.

这是一个改进的版本：

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

void sieve(long x, unsigned char primes[]) {
    long i, j;

    for (i = 0; i < x; i++) {
        primes[i] = i & 1;
    }
    primes[1] = 0;
    primes[2] = 1;
    /* loop through all odd numbers up to the sqrt(x) */
    for (i = 3; (j = i * i) < x; i += 2) {
        /* skip composite numbers */
        if (primes[i] == 0)
            continue;
        /* mark each odd multiple of i as composite */
        for (; j < x; j += i + i) {
            primes[j] = 0;
        }
    }
}

int main(int argc, char *argv[]) {
    long i, x, count;
    int do_count = 0;
    unsigned char *v;

    if (argc > 1) {
        x = strtol(argv[1], NULL, 0);
    } else {
        printf("enter x: ");
        if (scanf("%ld", &x) != 1)
            return 1;
    }

    if (x < 0) {
        x = -x;
        do_count = 1;
    }
    v = malloc(x);
    if (v == NULL) {
        printf("Not enough memory\n");
        return 1;
    }

    sieve(x, v);

    if (do_count) {
        for (count = i = 0; i < x; i++) {
            count += v[i];
        }
        printf("%ld\n", count);
    } else {
        for (i = 0; i < x; i++) {
            if (v[i] == 1) {
                printf("%ld\n", i);
            }
        }
    }
    free(v);
    return 0;
}

超过 500000 用 Eratosthenes 的方法

exceeding 500000 with the method of Erastosthenes

c

primes