为什么从 int i = 6 开始的 for 循环比 int i = 0 花费的时间更长？

Question

我已经用 C 编写了埃拉托色尼筛法，但是当我从 int i = 6 开始时，我的 for 循环需要更长的时间。

int *tmp = NULL;

tmp = malloc(sizeof(int) * 1000000);

tmp[0] = 2;
tmp[1] = 3;
tmp[2] = 5;

int prim_ = 3;
bool hasdiv = false;

clock_t t;
t = clock();
for(int i = 6; i < 1000000; i++) {
    for (int j = 0; j < prim_; j++){
        if (i % tmp[j] == 0) {
            hasdiv = true;
            break;
        }
    }
    if (!hasdiv) {
        prim_++;
        tmp[prim_] = i;
    }
    hasdiv = false;
}
t = clock() - t;
double tim = ((double)t) / CLOCKS_PER_SEC;

printf("%f",tim);

和

for(int i = 6; i < 1000000; i++) {

需要 8.4 秒

for(int i = 0; i < 1000000; i++) {

需要 0.009 秒。行为从何而来？

我使用 VS 19 社区和 MSVC 14.24.28314。

Answer 1

首先，请注意您的代码有一个错误，即 tmp[3] 永远不会被初始化：您从 3 开始 prim_ 并在分配给 tmp[prim_] 之前递增它.因此，每次 j==3 循环时，您都会读取未初始化的内存，并且您的代码具有未定义的行为。您可能想要交换 prim_++; tmp[prim_]=i; 行，或者只是写 tmp[prim_++]=i;.

解决这个问题后，想想当你使用 i==1 进行循环时会发生什么。 1 不能被任何大于 1 的整数整除，因此您的代码将断定它是质数，并将设置 tmp[3]=1。由于每个数字都可以被 1 整除，因此在外循环的每次后续迭代中，您将在 j==3 时立即跳出内循环。这显然比 j 必须一直上升到 prim_ 要快得多。它还将使您的程序变得毫无价值，因为它将决定没有超过 5 的素数。

大多数处理素数的逻辑都需要数字 1 的特例，这也不例外。对于您的程序来说，以小于 2 的 i 值开始确实没有任何意义。

为什么从 int i = 6 开始的 for 循环比 int i = 0 花费的时间更长？

Why does a for loop that start int i = 6 takes longer than int i = 0?

c

loops

for-loop

sieve-of-eratosthenes