2

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
pjs
  • 17,381
  • 4
  • 25
  • 47
陳韋勳
  • 21
  • 1
  • 1
    Other than 2, prime numbers are odd. Your code doesn't exploit that fact. Thus, there is an easy way to make it at least 50% faster. Since your code is working, consider posting this question on [codereview.se] rather than here -- but first read their posting guidelines if you do. – John Coleman Aug 24 '21 at 12:19
  • Maybe you can use this https://miraclelearningcentre.com/the-pattern-in-prime-numbers/ – mama Aug 24 '21 at 12:22
  • 3
    You could try Sieve of Eratosthenes. – Ram Aug 24 '21 at 12:24
  • 1
    I am puzzled that this was marked a duplicate of a question about `isPrime`, when this question is about *finding the next prime number*, not *testing if a given number is prime*. – Stef Aug 24 '21 at 14:18
  • @Stef: agreed, so why not vote to reopen? Algorithms for finding the next, or previous prime, may different than testing if a given number is prime. – President James K. Polk Aug 24 '21 at 16:04
  • 1
    @PresidentJamesK.Polk Done. – Stef Aug 24 '21 at 16:45

1 Answers1

1

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
kcsquared
  • 5,093
  • 1
  • 9
  • 35