找到小于或等于给定输入的最大素数的更快方法

Question

给定一个整数，我想找到它下面的最大素数。例如：

input 20 -> output 19
input 100 -> output 97.

我已经有了下面给出的简单程序，但我很好奇如何使它更快

def isPrime(x):
  for j in range(2,int(x**0.5)+1):
    if x%j==0:
      return False
  return True

def findPrimeNum(num):
  for i in range(num-1,1,-1):
    if isPrime(i):
      return i

findPrimeNum(600851475143)  # -> 600851475067

Answer 1

最好的方法可能是镜像几个数论库使用什么来实现一个有效的next_素数函数。基本布局与您的相同：一个isPrime（x）函数和一个循环倒计时。这为优化提供了两个方面

优化iPrime 推荐的方法是使用类似Python的gmpy2的数论库，以及类似Miller-Rabin的概率素性测试重复适当的次数。这可以很好地扩展较大的数字，甚至可以通过使用Miller-Rabin和enough small bases进行确定性素性测试

在可能的素数上优化迭代 已经有了一个comprehensive guide for optimizing next_prime in practice，它基本上涉及选择前k个素数（例如2、3和5）并计算所有可能是素数的乘积的剩余数。然后，不要迭代所有较小的数，只在这些剩余数之间跳跃。为了使其适用于先前的素数，我们只需在相反方向的余数之间跳跃

对于2、3和5，那些mod 30的残基是L=[1、7、11、13、17、19、23、29]。对于整数x>；30，假设x=30*q+r，在L上搜索小于r的最大元素，然后在该列表中向后迭代：

residues = [1, 7, 11, 13, 17, 19, 23, 29]
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]


def prevPrime(num):
    if num <= 2:
        return 0
    q, r = divmod(num, 30)
    if q == 0:
        return small_primes[bisect_left(small_primes, num) - 1]
    num = 30 * q
    if r <= 2:
        num -= 30
        q -= 1
        idx = len(residues) - 1
    else:
        idx = bisect_left(residues, r) - 1
    num += residues[idx]
    while not (isPrime(num)):
        idx -= 1
        if idx < 0:
            q -= 1
            idx = len(residues) - 1
        num = 30 * q + residues[idx]
    return num