C - 从特定的大范围中获取素数

Question

#include <stdio.h>
#include <math.h>
#define UPPER_LIMIT 2147483647
void sieve(unsigned long int n, unsigned long int primes[]);  
main()  
{  
    unsigned long int low, up, steps;  
    unsigned long int v[UPPER_LIMIT];  
    sieve(UPPER_LIMIT, v);  
    scanf("%ld\n",&steps);  
    for (unsigned long int i=0;i<steps;i++){  
        scanf("%ld %ld\n",&low,&up);  
        for(unsigned long int j=low; j<up; j++){  
            if (v[j] == 1){  
                printf("%ld\n",j);  
            }  
        }   
    }  
}  
void sieve(unsigned long int n, unsigned long int primes[])  
{  
    for (unsigned long int i=0;i<n;i++){  
        primes[i]=1;  
    }  
    primes[0]=0,primes[1]=0;   

    for (unsigned long int i=2;i<sqrt(n);i++) {  
        for (unsigned long int j=i*i;j<n;j+=i){  
            primes[j] = 0;  
        }  
    }  
}  

我正在尝试解决打印特定范围内的素数的问题。 首先 scanf 我们得到要审查的案例数量。该范围由标准输入的下一行给出，例如 (1 10) 上限值可以是最大值 2147483647。我正在使用埃拉斯托斯特筛法来查找素数。之后我想按升序 printf 素数。不幸的是，我遇到了运行时错误，我认为这是因为我试图创建的数组非常大。我需要有关问题的可能解决方案的建议。

标准输入示例:

1  
1 10

标准输出示例:

2  
3  
7  

Answer 1

使用unsigned long是没有意义的。仅存储 0 的数组或1 .

您只需要2147483647 / 8位来存储您需要的所有信息，因此您应该声明一个最多 2147483647 / 8 + 1 的数组字节:

const unsigned int SIZE = 1 + (2147483647 / 8);
unsigned char primes[SIZE];

或者更好的是，通过堆分配:

const unsigned int SIZE = 1 + (2147483647 / 8);
unsigned char *primes = (unsigned char*)malloc(SIZE);

数组初始化变为:

for (unsigned i = 0; i < SIZE ; i++ ){  
    primes[i] = 1;
}

可以使用按位运算符 >> 来访问数组的各个位。 , << ，和& 。实现此功能将作为练习，因为这看起来像大学练习。