algorithm - 如何创建最紧凑的映射 n → isprime(n) 直到限制 N？

Question

自然地，对于 bool isprime(number) 会有一个我可以查询的数据结构。
我定义最佳算法，即生成在 (1, N] 范围内内存消耗最低的数据结构的算法，其中 N 是一个常数。
只是我正在寻找的一个例子:我可以用一位表示每个奇数，例如对于给定的数字范围 (1, 10]，从 3 开始:1110

下面的字典还能挤多点吧？我可以通过一些工作消除五的倍数，但以 1、3、7 或 9 结尾的数字必须存在于位数组中。

我该如何解决这个问题？

Answer 1

一般素数测试最快的算法是AKS .维基百科文章对其进行了详细描述，并提供了原始论文的链接。

如果您想找到大数，请查看具有特殊形式的素数，例如 Mersenne primes .

我通常实现的算法(易于理解和编码)如下(Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

它是经典 O(sqrt(N)) 算法的变体。它利用素数(2 和 3 除外)的形式为 6k - 1 或 6k + 1 的事实，并且只查看这种形式的除数。

有时，如果我真的想要速度并且范围有限，我会根据Fermat's little theorem 实现伪素数测试。 .如果我真的想要更快的速度(即完全避免 O(sqrt(N)) 算法)，我会预先计算误报(参见 Carmichael 数字)并进行二进制搜索。这是迄今为止我实现过的最快的测试，唯一的缺点是范围有限。