Long long int 使我的埃拉托色尼筛法超慢？

Question

我有一个程序要求我找到 10**10-1 (10,000,000,000) 之前的素数。我写了一个埃拉托色尼筛法来做这个，它在 10**9 (1,000,000,000) 时工作得很好（而且准确）。我通过让它计算它找到的素数的数量来确认它的准确性，并且它匹配 the chart found here. 上的值 50,847,534 我使用 unsigned int 作为存储类型并且它在大约 30 秒内成功找到了所有素数.

但是，10**10 要求我使用更大的存储类型：long long int。一旦我切换到这个，程序就会运行显着变慢（它已经超过 3 个小时并且仍在运行）。这是相关代码：

typedef unsigned long long ul_long;
typedef unsigned int u_int;

ul_long max = 10000000000;                            
u_int blocks = 1250000000;
char memField[1250000000];     

char mapBit(char place) {             //convert 0->0x80, 1->0x40, 2->0x20, and so on
    return 0x80 >> (place);
}

for (u_int i = 2; i*i < max; i++) {

    if (memField[i / 8] & activeBit) {               //Use correct memory block
        for (ul_long n = 2 * i; n < max; n += i) {
            char secondaryBit = mapBit(n % 8);       //Determine bit position of n
            u_int activeByte = n / 8;                //Determine correct memory block
            if (n < 8) {                             //Manual override memory block and bit for first block
                secondaryBit = mapBit(n);
                activeByte = 0;
            }
            memField[activeByte] &= ~(secondaryBit);  //Set the flag to false
        }
    }
    activeBit = activeBit >> 1;                       //Check the next
    if (activeBit == 0x00) activeBit = 0x80;
}

我认为由于 10**10 比 10**9 大 10 倍，所以它应该花费 10 倍的时间。这其中的漏洞在哪里？为什么更改为 long long 会导致如此严重的性能问题，我该如何解决？我认识到数字变大了，所以它应该慢一些，但只到最后。有什么我想念的吗？

注意：我知道 long int should technically be large enough 但我的 limits.h 说它不是，即使我正在编译 64 位。这就是为什么我使用 long long int 以防万一有人想知道。另外，请记住，我没有接受过计算机科学培训，只是一个爱好者。

编辑：只是运行它在 "Release" 中作为 x86-64 以及建议的一些调试语句。我得到以下输出：

看来我达到了 u_int 的极限。我不知道为什么 i 变得那么大。

Answer 1

您的程序在 for (u_int i = 2; i*i < max; i++) 中有一个无限循环。 i 是一个 unsigned int，所以 i*i 以 32 位换行并且总是小于 max。将 i 设为 ul_long.

请注意，对于位 0 到 7，您应该使用从 1 到 0x80 的更简单的位模式。

这是一个完整的版本：

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

typedef unsigned long long ul_long;
typedef unsigned int u_int;

#define TESTBIT(a, bit)   (a[(bit) / 8] & (1 << ((bit) & 7)))
#define CLEARBIT(a, bit)  (a[(bit) / 8] &= ~(1 << ((bit) & 7)))

ul_long count_primes(ul_long max) {
    size_t blocks = (max + 7) / 8;
    unsigned char *memField = malloc(blocks);
    if (memField == NULL) {
        printf("cannot allocate memory for %llu bytes\n",
               (unsigned long long)blocks);
        return 0;
    }
    memset(memField, 255, blocks);
    CLEARBIT(memField, 0);  // 0 is not prime
    CLEARBIT(memField, 1);  // 1 is not prime
    // clear bits after max
    for (ul_long i = max + 1; i < blocks * 8ULL; i++) {
        CLEARBIT(memField, i);
    }

    for (ul_long i = 2; i * i < max; i++) {
        if (TESTBIT(memField, i)) {           //Check if i is prime
            for (ul_long n = 2 * i; n < max; n += i) {
                CLEARBIT(memField, n);                   //Reset all multiples of i
            }
        }
    }
    unsigned int bitCount[256];
    for (int i = 0; i < 256; i++) {
        bitCount[i] = (((i >> 0) & 1) + ((i >> 1) & 1) +
                       ((i >> 2) & 1) + ((i >> 3) & 1) +
                       ((i >> 4) & 1) + ((i >> 5) & 1) +
                       ((i >> 6) & 1) + ((i >> 7) & 1));
    }
    ul_long count = 0;
    for (size_t i = 0; i < blocks; i++) {
        count += bitCount[memField[i]];
    }
    printf("count of primes up to %llu: %llu\n", max, count);
    free(memField);
    return count;
}

int main(int argc, char *argv[]) {
    if (argc > 1) {
        for (int i = 1; i < argc; i++) {
            count_primes(strtoull(argv[i], NULL, 0));
        }
    } else {
        count_primes(10000000000);
    }
    return 0;
}

10^9 在 10 秒内完成，10^10 在 131 秒内完成：

count of primes up to 1000000000: 50847534
count of primes up to 10000000000: 455052511

Long long int 使我的埃拉托色尼筛法超慢？

Long long int makes my Sieve of Eratosthenes super slow?

c

performance

sieve

sieve-of-eratosthenes