c - Eratosthenes 位数组筛法

Question

我正在尝试使用带位数组的埃拉托色尼筛法查找素数，但我使用的是无符号整数数组。我需要能够生成多达 2,147,483,647 个素数。我的代码有效并且可以生成大约 10,000,000，但是当我增加数组的大小时以容纳更大的数字时它失败了。有人可以指导我如何将位 vector 与 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;
}

Answer 1

我绝对不会使用位数组，而是使用原生 int 数组(64 位或 32 位取决于体系结构)并环绕一个函数以将普通数字重新映射到正确的位置并使用位 | 和 &。

还要考虑去掉偶数，几乎没有一个是素数。因此，您可以将前 128 个数字存储在第一个 64 位数字中，接下来的 128 个数字存储在第二个数字中，依此类推。

听起来有点复杂，但实际操作起来很有趣!

欧拉计划似乎产生了一些非常好的解决方案。

好处是:筛选时不需要重新计算偶数-奇数转换，但是您可以取消设置每三位用于筛选 3，每五位取消设置用于筛选 5 等。

如果您需要快速的 Java 解决方案作为详细引用，请加入聊天。

EDIT4:更正了工作代码，但仍然很慢。备注:记得使用 calloc!

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

typedef unsigned long long number;

number lookFor = 2147483648ULL;
number max = 2147483648ULL*10ULL; // hopefully more then every 10th uneven number is prime

unsigned long * isComposite;

number bitslong = CHAR_BIT*sizeof(long);

time_t rawtime;
struct tm * timeinfo;
char buffer[80];

// is not called during sieve, only once per sieving prime 
// and needed for reading if a number is prime
inline long getParts(number pos, number *slot, unsigned int *bit){
    *slot = pos / bitslong;
    *bit = (unsigned int)(pos % bitslong);
}

int isPrime(number n){
    if(n == 1){
        return 0;
    }

    if(n < 4){
        return 1;
    }

    if((n%2) == 0){
        return 0;
    }

    number slot=0;
    unsigned int bit=0;
    number pos = (number)(n-3)/2;
    getParts(pos, &slot, &bit);
    // printf("? n=%lld  pos = %lld slot = %lld bit = %lu ret %d \n", n, pos, slot, bit, !(isComposite[slot] & (1<<bit)));
    return !(isComposite[slot] & (1UL<<bit));
}

// start sieving at offset (internal position) offset with width step 
int doSieve(number offset, number step){
    rawtime = time(0);
    time (&rawtime);
    timeinfo = localtime (&rawtime);

    strftime(buffer, 80, "%Y-%m-%d %H:%I:%S", timeinfo);
    unsigned int bit=0;
    number slot=0;
    getParts(offset, &slot, &bit);
    printf("doSieve %s  %lld %lld  %lu \n", buffer, offset, step, isComposite[slot]);

    while(slot < max/bitslong){
        slot += (step + bit)/bitslong;
        bit = (step + bit) % bitslong;
        isComposite[slot] |= (1UL << bit);
    } 
    return 1;
}

int sieve(){
    number spot;
    spot=1;
    number pos;
    pos = 0;
    while(spot < 1 + sqrt((float)max)){
        spot+=2;
        if(! isPrime(spot)){
            pos++;
            continue;
        }
        doSieve(pos, spot);
        pos++;
    }
}

void main(int argc, char *argv[]){
    if(argc > 1){
        char *tp = malloc(sizeof(char*));
        max = strtol(argv[1], &tp, 10);
    }
    printf("max %lld , sq %ld, malloc: %lld\n", max, (long)(1 + sqrt((float)max)), 1+max/bitslong);
    isComposite = calloc((2+max/bitslong), sizeof(unsigned long)) ;
    if(! isComposite){
        printf("no mem\n");
        exit(5);
    }
    sieve();
    number i;
    number found = 0;
    for(i = 1; i<max && found < lookFor; i++){
        if(isPrime(i)){
            found++;
            // printf(" %30lld %30lld \n", found, i);
            if(found % 10000 == 0 ){
                printf("%30lld %30lld \n", found, i);
            }
        }
        /*
        if(i % 1000 == 17){
            printf("%5lld %5lld \n", i, found);
        }
        */
    }
}