Find the next prime number in Python

Question

I have a function that takes a number (for example, 5) and returns the first prime number after the input number (in this case, it would be 7).

This is my code:

def prime(n):
    np=[]
    isprime=[]
    for i in range (n+1,n+200):
        np.append(i)
    for x in range(2,199):
        for j in np:
            if x%j!=0:
                isprime.append(x)
    return min(isprime)

However, this code doesn't work (it always returns 2). Where is the mistake?

Answer 1

My is prime code is very fast for larger numbers. It will find the previous and next prime for a 15 digit number in a few seconds. For really fast checks use GMPY2 is_prime() GMPY2 is_prime lets the code find the next and previous primes of a 40 digit number in about a microsecond. I only check numbers that are 6k+1 or 6k-1 so we only look for numbers likely to be prime. The gmpy2 version seems to be twice as fast as sympy's nextprime() About the same time to get twice as many numbers (Previous and next)

#from gmpy2 import is_prime
from datetime import timedelta
import sys,time
def isPrime(n):  
    if (n <= 1):  
        return False      
    if (n <= 3):  
        return True        
    if (n%2 == 0 or n%3 == 0):  
        return False      
    for i in range(5,int(n**.5)+1): 
        if (n%i == 0 or n%(i+2) == 0):  
            return False          
    return True  

def prime_near(n,prev=False): 
    start = n-n%6+5  # get nearby 6k-1
    k6,start,stop = (-6,start-6,1) if prev else (6,start,n+80*6)  
    for i in range(start,stop,k6):
        # use GMPY2 is_prime() for really fast checks
        if prev:
            if isPrime(i+2): 
                return i+2
            if isPrime(i): 
                return i
        else: # next
            if isPrime(i): 
                return i
            if isPrime(i+2): 
                return i+2
    return -1

if __name__ == '__main__':
    N = 1000
    start_time = time.time() 
    args = len(sys.argv)
    if args > 1:
            N = int(sys.argv[1])
    print(f"Code will find nearest primes to {N:,}.")

    print(f"\nPrimes near to {N:,} are {prime_near(N,prev=True):,} and {prime_near(N):,}\n ") 

    print(f"The search took {str(timedelta(seconds=time.time()-start_time))}.")

Here is some output:

$ python next_prime.py 100000345

Code will find nearest primes to 100,000,345.

Primes near to 100,000,345 are 100,000,279 and 100,000,357

The search took 0:00:00.003622.

$ python next_prime.py 100000324234234

Code will find nearest primes to 100,000,324,234,234.

Primes near to 100,000,324,234,234 are 100,000,324,234,207 and 100,000,324,234,259
The search took 0:00:04.497683.

This is using GMPY2's is_prime() to replace my isPrime():

$ python next_prime.py 100000046328146378126437821467823164783216478361478361784623781463784781 Code will find nearest primes to 100,000,046,328,146,378,126,437,821,467,823,164,783,216,478,361,478,361,784,623,781,463,784,781.

Primes near to 100,000,046,328,146,378,126,437,821,467,823,164,783,216,478,361,478,361,784,623,781,463,784,781 are 100,000,046,328,146,378,126,437,821,467,823,164,783,216,478,361,478,361,784,623,781,463,784,719 and 100,000,046,328,146,378,126,437,821,467,823,164,783,216,478,361,478,361,784,623,781,463,784,799

The search took 0:00:00.000410.

Answer 2

n = int(input("Enter a number"))

while True:
    n+=1
    for  x in range(2,n):
        if n%x==0:
           break
    else:
         print("next prime number is",n)
         break

Answer 3

https://www.geeksforgeeks.org/python-simpy-nextprime-method/

from sympy import *
  
# calling nextprime function on differnet numbers 
nextprime(7) 
nextprime(13) 
nextprime(2)

Output:

11 17 3

Answer 4

Try this one, the most pythonic and clear way to do this that I found (but probably not the most efficient):

def is_prime(x):
    return all(x % i for i in range(2, x))

def next_prime(x):
    return min([a for a in range(x+1, 2*x) if is_prime(a)])

print(next_prime(9))

Answer 5

Try this one:

def find_next_prime(n):
    return find_prime_in_range(n, 2*n)

def find_prime_in_range(a, b):
    for c in range(a, b):
        for i in range(2, c):
            if c % i == 0:
                break
        else:
            return c
    return None

def main():
    n = int(input('Find the next prime number from: '))
    print(find_next_prime(n+1))

if __name__ == '__main__':
    main()

Answer 6

def is_prime(n):
    # Corner case
    if n <= 1:
        return False
    # Check from 2 to n-1
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def first_prime_over(n):
    prime_number = (i for i in range(n) if is_prime(i))
    try:
        for i in range(0,n):
            (next(prime_number))
    except StopIteration:
        prime_number_next = (i for i in range(n,n+1000) if is_prime(i))
        print(next(prime_number_next))
first_prime_over(10)

Answer 7

Here is one working sample.

inputNumber = int(input("Enter number to find next prime: "))

def nextPrime(inputNum):

    for nextNumToChk in range(inputNum+1, inputNum +200):
        if nextNumToChk > 1:
            # If num is divisible by any number between 2 and val, it is not prime
            for i in range(2, nextNumToChk):
                if (nextNumToChk % i) == 0:
                    break
            else:
                #found the prime
                return nextNumToChk

result = nextPrime(inputNumber)
print "Next Prime is : ",result

Output:-

Enter number to find next prime: 5
Next Prime is :  7

Answer 8

This code working.

def prime(n):
    next_prime = n + 1
    prime = True
    while True:
        for i in range(2, next_prime):
            if next_prime%i ==0:
                prime = False
                break
        if prime:
            return next_prime
        else:
            next_prime = next_prime + 1
            if next_prime % 2 == 0:
                next_prime = next_prime + 1
            prime = True


if __name__=="__main__":
    print(prime(5))

Answer 9

You have a few mistakes, most notably np is clearly meant to be the potential primes (it starts at n+1 which is the first potential number that fits your critera "the first prime number after the input number"), and yet you add x to your prime list, which is from range(2,199), you should be using:

isprime.append(j)

Your primality test is also the wrong way round as a result, you should be using:

j % x != 0

Lastly, you can't append a number if that condition is true in one case, it has to be true in all cases (where x is an integer which satisfies 2 <= x < j), because of this you should switch your second set of for loops around (the x loop should be the inner loop), and you should also only loop up to j-1 (the number being tested). Additionally, you should instead choose to not add an item if j % x == 0:

for ...:
    val_is_prime = True
    for ...:
        if j % x == 0:
            val_is_prime = False
            break
    if val_is_prime:
        isprime.append(j)

This results in the following code:

def prime(n):
    np=[]
    isprime=[]
    for i in range (n+1,n+200):
        np.append(i)
    for j in np:
        val_is_prime = True
        for x in range(2,j-1):
            if j % x == 0:
                val_is_prime = False
                break
        if val_is_prime:
            isprime.append(j)
    return min(isprime)

And test run:

>>> prime(5)
7
>>> prime(13)
17
>>> prime(23)
29

---

Note that there's several other efficiency improvements that could be made, but this answer focuses on the mistakes rather than improvements