如何创建最紧凑的映射 n → isprime(n) 直到极限 N? [英] How to create the most compact mapping n → isprime(n) up to a limit N?

问题描述

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

Naturally, for bool isprime(number) there would be a data structure I could query.
I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a constant.
Just an example of what I am looking for: I could represent every odd number with one bit e.g. for the given range of numbers (1, 10], starts at 3: 1110

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

The following dictionary can be squeezed more, right? I could eliminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits.

我该如何解决问题?

推荐答案

一般素数测试最快的算法是 AKS.维基百科文章详细描述了它并链接到原始论文.

The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper.

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

If you want to find big numbers, look into primes that have special forms like Mersenne primes.

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

The algorithm I usually implement (easy to understand and code) is as follows (in 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 形式的事实，并且只查看这种形式的除数.

It's a variant of the classic O(sqrt(N)) algorithm. It uses the fact that a prime (except 2 and 3) is of form 6k - 1 or 6k + 1 and looks only at divisors of this form.

有时，如果我真的想要速度并且范围有限，我会基于 费马小定理.如果我真的想要更快的速度(即完全避免 O(sqrt(N)) 算法)，我会预先计算误报(参见 Carmichael 数字)并进行二分查找.这是迄今为止我实现的最快的测试，唯一的缺点是范围有限.

Sometimes, If I really want speed and the range is limited, I implement a pseudo-prime test based on Fermat's little theorem. If I really want more speed (i.e. avoid O(sqrt(N)) algorithm altogether), I precompute the false positives (see Carmichael numbers) and do a binary search. This is by far the fastest test I've ever implemented, the only drawback is that the range is limited.

这篇关于如何创建最紧凑的映射 n → isprime(n) 直到极限 N?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！