我正在尝试使用带有位数组的 Eratosthenes 筛来查找素数,但我使用的是无符号整数数组。我需要能够生成多达 2,147,483,647 个素数。我的代码可以工作并且可以生成大约 10,000,000,但是当我增加数组的大小以容纳更大的数字时,它会失败。有人可以指导我如何将位向量与 c(不是 c++)一起使用。谢谢
这是我的代码:
#include <stdio.h>
#include <stdlib.h>
#define MAXBYTES 2000000
#define MAX 50000000
#define BITSIZE 32
void ClearBit(unsigned int [], unsigned int);
void SetBit(unsigned int [], unsigned int);
int BitVal(unsigned int [], unsigned int);
void PrintBitStream(unsigned int [], unsigned long);
void PrintBitStreamData(unsigned int[], unsigned long);
int Sieve(unsigned int[], unsigned int, unsigned int);
int main(int argc, char ** argv) {
unsigned int maxsize = MAX;
unsigned int i;
//Set Bit Array
unsigned int BitArray[MAXBYTES] = {0};
SetBit(BitArray, 0);
SetBit(BitArray, 1);
i = 2;
for (;i < maxsize;i++){
if(Sieve(BitArray, i, maxsize)==0)
break;
}
PrintBitStreamData(BitArray, maxsize-1);
return EXIT_SUCCESS;
}
void PrintBitStreamData(unsigned int BitArray[], unsigned long maxsize) {
unsigned int i;
for (i = 0; i < maxsize; i++)
if (!BitVal(BitArray, i))
printf("%ld ", i);
printf("\n");
}
void PrintBitStream(unsigned int BitArray[], unsigned long maxsize) {
unsigned int i;
for (i = 2; i < maxsize; i+=2)
printf("%d", BitVal(BitArray, i));
printf("\n");
}
void SetBit(unsigned int BitArray[], unsigned int pos) {
BitArray[pos / BITSIZE] |= 1 << (pos % BITSIZE);
}
void ClearBit(unsigned int BitArray[], unsigned int pos) {
BitArray[pos / BITSIZE] &= ~(1 << (pos % BITSIZE));
}
int BitVal(unsigned int BitArray[], unsigned int pos) {
return ((BitArray[pos / BITSIZE] & (1 << (pos % BITSIZE))) != 0);
}
int Sieve(unsigned int BitArray[], unsigned int p, unsigned int maxsize) {
unsigned int i;
unsigned int j;
j = 0;
for (i = 2 * p; i < maxsize; i += p) {
SetBit(BitArray, i);
j++;
}
return j;
}