Faster way to find the biggest prime number less than or equal to the given input

user_10223580 0
Viewed 663

Given an integer number, I want to find the biggest prime number under it. For example:

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

I already have the simple program given below, but I'm curious about how to make it faster.

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
primes algorithm python
1 Answers

The best way is probably to mirror what several number theory libraries use to implement an efficient next_prime function. The basic layout is identical to yours: an isPrime(x) function, and a loop counting down. Those provide two areas for optimization.

Optimizing isPrime The recommended approach is to use a number theory library for Python like gmpy2, and a probabilistic primality test like Miller-Rabin repeated an appropriate number of times. This scales fairly well with larger numbers, and you can even get a deterministic primality test by using Miller-Rabin with enough small bases.

Optimizing iteration over possible primes There is already a comprehensive guide for optimizing next_prime in practice, which basically involves choosing the first k primes (e.g. 2, 3 and 5) and computing all residues modulo their product that could potentially be a prime. Then, rather than iterating over all smaller numbers, you jump between those residues only. To adapt this to previousPrime, we just jump between residues in the opposite direction.

For 2, 3, and 5, those residues mod 30 are L = [1, 7, 11, 13, 17, 19, 23, 29]. For an integer x > 30, say x = 30*q + r, you would do a binary search over L for the largest element less than r, and iterate backwards in this list:

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
user_167571740
Related