寻找最近的小素数的快速算法

Question

如果给定的数字是10，我们必须返回7(因为它是最近的较小的质数)

我能想到的方法是这样的：- Mainloop:测试给定的数字是否为质数(通过应用质数测试)，如果它是质数，则返回该数字，否则将该数字减去1并转到Mainloop。

但我必须在很长很长的整数范围内工作，这需要很多时间。

有没有更好的方法，如果我只使用上面的方法，那么我应该使用哪个质数测试？谢谢:)

Answer 1

如果输入的大小是有界的，那么在预计算素数表中查找可能是最快的。

Answer 2

除了以上，还要注意，Bertrand's postulate指出，在n<p<2n-2处，总是存在至少一个素数p。这就给了你一个上限。

Answer 3

这里是Daniel Fischer在他的评论中提到的Baillie-Wagstaff伪伪性测试的伪代码实现。我们从一个简单的Eratosthenes筛子开始，我们稍后会用到它。

function primes(n)
    ps := []
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            ps.append(p)
            for i from p * p to n step p
                sieve[i] := False
    return ps

powerMod函数将所有以m为模的计算的基数b提升到指数e；它比先进行求幂，然后取结果的模要快得多，因为中间的计算量会很大。

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

数论中的jacobi函数告诉我们a是否是二次剩余mod p。

function jacobi(a, p)
    a := a % p
    t := 1
    while a != 0
        while a % 2 == 0
            a := a / 2
            if p % 8 == 3 or p % 8 == 5
                t := -t
        a, p := p , a # swap
        if a % 4 == 3 and p % 4 == 3
            t := -t
        a := a % p
    if p == 1 return t else return 0

Gary Miller的强伪素性检验是基于Pierre de Fermat的小定理，该小定理指出:如果p是素数，则对任意a != 0，a^ (p - 1) == 1 (mod )。米勒的测试在某种程度上比费马的测试更强，因为它不会被卡迈克尔数字所欺骗。

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d % 2 == 0
        d := d / 2; s := s + 1
    t = powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1 return ProbablyPrime
        t := (t * t) % n; s := s - 1
    return Composite

Miller-Rabin测试执行k个强伪质测试，其中k通常在10到25之间。强伪病毒测试是可以被愚弄的，但如果您执行了足够多的测试，那么被愚弄的可能性非常小。

function isPrime(n) # Miller-Rabin
    for i from 1 to k
        a := randInt(2 .. n-1)
        if not isStrongPseudoprime(n, a)
            return Composite
    return ProbablyPrime

这个质数测试对于大多数目的来说已经足够了，而且足够快。但如果你想要更强一点和更快一点的东西，可以使用基于Lucas链的测试。这是Lucas链的计算。

function chain(n, u, v, u2, v2, d, q, m)
    k := q
    while m > 0
        u2 := (u2 * v2) % n; v2 := (v2 * v2 - 2 * q) % n
        q := (q * q) % n
        if m % 2 == 1
            t1 := u2 * v; t2 := u * v2
            t3 := v2 * v; t4 := u2 * u * d
            u, v := t1 + t2, t3 + t4
            if u % 2 == 1 u := u + n
            if v % 2 == 1 v := v + n
            u, v, k := (u / 2) % n, (v / 2) % n), (q * k) % n
        m := floor(m / 2)
    return u, v, k

由于John Selfridge的缘故，使用算法初始化Lucas链是很常见的。

function selfridge(n)
    d, s := 5, 1; ds := d * s
    repeat
        if gcd(ds, n) > 1 return ds, 0, 0
        if jacobi(ds, n) == 1 return ds, 1, (1 - ds) / 4
        d, s := d + 2, s * -1; ds := d * s

然后，Lucas伪素数测试确定一个数是质数还是可能是复合数。像费马测试一样，它有两种风格，既有标准的，也有强的，而且像费马测试一样，它可以被愚弄，尽管使用费马测试的错误是，合成数可能被错误地报告为素数，但对于卢卡斯测试，错误是质数可能被错误地报告为合成。

function isLucasPseudoprime(n) # standard
    d, p, q := selfridge(n)
    if p == 0 return n == d
    u, v, k := chain(n, 0, 2, 1, p, d, q, (n + 1) / 2)
    return u == 0

function isLucasPseudoprime(n) # strong
    d, p, q := selfridge(n)
    if p == 0 return n == d
    s, t := 0, n + 1
    while t % 2 == 0
        s, t := s + 1, t / 2
    u, v, k := chain(n, 1, p, 1, p, d, q, t // 2
    if u == 0 or v == 0 return Prime
    r := 1
    while r < s
        v := (v * v - 2 * k) % n; k := (K * k) % n
        if v == 0 return Prime
    return ProbablyComposite

那么贝利-瓦格斯塔夫测试就很简单了。首先检查输入是否小于2或者是一个完美的平方(检查平方根是否为整数)。然后尝试除以小于100的素数，快速找到大多数组合，最后对基数2进行强伪素数测试(有些人将强伪素数测试添加到基数3，以额外确定)，然后进行Lucas伪素数测试进行最终确定。

function isPrime(n) # Baillie-Wagstaff
    if n < 2 or isSquare(n) return False
    for p in primes(100)
        if n % p == 0 return n == p
    return isStrongPseudoprime(n, 2) \
       and isLucasPseudoprime(n) # standard or strong

贝利-瓦格斯塔夫测试没有已知错误。

一旦你有了一个很好的素数测试，你就可以通过从n开始倒数，在第一个素数处停止，找到小于n的最大素数。

如果您对质数编程感兴趣，我建议在我的博客中使用this essay，或者许多其他与质数相关的博客条目，您可以使用博客中的搜索功能找到它们。