c - 为什么这个素数算法有效？

Question

#define _CRT_SECURE_NO_WARNINGS

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

int main() {
    int anz;
    scanf("%d", &anz);
    time_t start = time(0);
    int *primZ = malloc(anz * sizeof(int));
    primZ[0] = 2;
    int Num = 0;

    for (int i = 1, num = 3; i < anz; num += 2) {
        for (int j = 1; j < i; j++) {
            if (num % primZ[j] == 0) {
                num += 2;
                j = 0;
            }

            //this part
            if (primZ[j] > i / 2)
                break;
        }

        primZ[i] = num;
        i++;
        printf("%d ,",num);
    }

    time_t delta = time(0) - start;
    printf("%d", delta);
    getchar();
    getchar();
    return 0;
}

代码工作得很好，问题是为什么。 if(primZ[j] > i/2) 部分使程序快 2 - 3 倍。它实际上是 if(primZ[j] > num/3) 这很有意义，因为 num 只能是奇数。但它是找到的素数的数量。对我来说完全是无稽之谈。请解释。

Answer 1

您可以通过检查素数是否可以被已找到的素数整除来检查素数是否为合素数。但在这样做时，您只需检查并包括数字的平方根，因为任何大于该数字的平方根的数字都会留下小于数字平方根的数字。

例如 33 是​​合数，但您只需检查最大为 5 的数字即可意识到，您不需要检查它是否可以被 11 整除，因为它剩下我们已经检查过的 3 (33/11=3) .

这意味着您可以通过以下方式改进您的算法

    for (int j = 1; j < i; j++) {
        if( primZ[j]*primZ[j] > num )
             break;

        if (num % primZ[j] == 0) {
            num += 2;
            j = 0;
        }
    }

与 i/2 的切割相比，您可以逃脱的原因是由于素数的分布。质数计数函数约为 i = num/log(num)，然后您得到 i/2 > sqrt(num)。