使用C计算给定long int范围内的素数

Question

嗯，在 SO 和其他论坛中有很多这样的问题。然而，这些都没有帮助。

我用“C”编写了一个程序来查找一定范围内的质数个数。 long int 中的范围 i。我正在使用 Sieve of Eratosthenes"算法。我正在使用一个长整数数组来存储从 1 到极限的所有数字。如果不使用数组，我想不出更好的方法来实现。代码工作正常，直到 10000000。但在那之后，它会耗尽内存并退出。下面是我的代码。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef unsigned long uint_32;

int main() {

    uint_32 i, N, *list, cross=0, j=4, k, primes_cnt = 0;
    clock_t start, end;
    double exec_time;

    system("cls");
    printf("Enter N\n");
    scanf("%lu", &N);
    list = (uint_32 *) malloc( (N+1) * sizeof(uint_32));
    start = clock();
    for(i=0; i<=N+1; i++) {
        list[i] = i;
    }

    for(i=0; cross<=N/2; i++) { 
        if(i == 0)
            cross = 2;
        else if(i == 1)
            cross = 3;
        else {

            for(j=cross+1; j<=N; j++) {
                if(list[j] != 0){

                    cross = list[j];
                    break;
                }
            }
        }

        for(k=cross*2; k<=N; k+=cross) {
            if(k <= N)
                list[k] = 0;
        }
    }

    for(i=2; i<=N; i++) {

        if(list[i] == 0)
            continue;
        else
            primes_cnt++;
    }

    printf("%lu", primes_cnt);
    end = clock();
    exec_time = (double) (end-start);
    printf("\n%f", exec_time);
    return 0;
}

我被困住了，想不出更好的方法来实现这一目标。任何帮助将不胜感激。谢谢。

编辑:

我的目标是生成并打印所有低于该范围的素数。由于打印需要花费大量时间，所以我想到了把第一步做好。

Answer 1

还有其他算法不需要您生成最多 N 个素数来计算 N 以下素数的个数。最容易实现的算法是 Legendre Prime Counting。该算法要求您仅生成 sqrt(N) 个素数以确定 N 以下素数的个数。

算法背后的思想是

pi(n) = phi(n, sqrt(n)) + pi(sqrt(n)) - 1

where
   pi(n) = number of prime below N
   phi(n, m) = number of number below N that is not divisible by any prime below m.

这意味着 phi(n, sqrt(n)) = sqrt(n) 到 n 之间的素数。关于phi的计算方法，可以到以下链接(Feasible implementation of a Prime Counting Function)

之所以效率更高，是因为计算 phi(n, m) 比计算 pi(n) 更容易。假设我要计算 phi(100, 3) 意味着有多少个小于或等于 100 的数字不能被 2 和 3 整除。您可以按以下步骤操作。 phi(100, 3) = 100 - 100/2 - 100/3 + 100/6。