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

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

这是有道理的，因为如果 n 有两个因子，其中一个肯定小于或等于 n/2，也就是说程序在 primZ 中找不到 i 的因子小于或等于 i/2 这意味着没有 i 的因数 - 当然除了 1 -。

意义primZ按升序排列j只增加，当primeZ[j] > i/2时表示primZ中i的因子没有小于i/2。

P.S.The 开始搜索的点在 for 语句的第一部分中说明 num=3 ，重复语句 num += 2 确保您只测试奇数

Answer 2

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

例如 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)。

Answer 3

原因是实际的界限比 num/3 更紧——你可以使用：

if (primZ[j] > sqrt(num))

that的原因是如果一个大于num的平方根的素数整除num，那么一定还有一个比num更低的素数确实如此（因为这样除法的结果必须小于平方根）。

这意味着只要 i/2 高于 sqrt(num)，代码就可以工作。发生的情况是，小于某个数的素数的增长 比该数的平方根快 ，这意味着（完全意外地）i/2 是可以安全使用的界限。

您可以查看 i 值的行为方式 here - 他们称之为 pi(x)，即小于 x 的素数数。

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

Why does this prime number algorithm work?

c

primes