Trying to find the next prime number

[FirstBornAlbratross]

Hi all,

My exercise for today (not for school) is for the user to enter a number and then I have to find the next prime number and print it.

This is what I've got so far (it doesn't work):

def nextPrime():
    num = int(input("Enter a number: "))
    
    next_num = num + 1
    
    while True:
        for i in range(2, next_num):
            if (next_num % i) == 0:
                next_num += 1
            else:
                break
                print(f"The next prime number is {next_num}.")
                
nextPrime()

I thought my logic was good, but apparently not. Any ideas?

Thanks.

Edit: I don't know how to make my code more readable on this site. Does anyone know?

Yoriz write Aug-08-2023, 06:38 PM:
Please post all code, output and errors (in it's entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.

[deanhystad]

Once you enter the loop it does not care if you change next_num, so your outer loop only tests if num + 1 is prime, and it doesn't do that correctly.

This is not a good test for prime:

        for i in range(2, next_num):
            if (next_num % i) == 0:
                next_num += 1
            else:
                break
                print(f"The next prime number is {next_num}.")

Let's say next_num = 9. You test if 9 is evenly divisible by 2. 9 % 2 == 1. It is not divisible by 2, so according to your program it is prime.

Finding only one factor is enough to determine a number is not prime. You need to test all possible factors before you can say a number is prime.

[FirstBornAlbratross]

Yeah, I scrapped my old code in favour of some new borrowed code.

This one works like a charm:

num = int(input("Enter a number: "))

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(f"The next prime number is {next_prime(num)}")

[deanhystad]

Your solution does a lot of extra math. Even for relatively small prime numbers this is doing thousands of times more modulo divisions that are needed.

This is your solution, modified to count the number of modulo divisions.

def is_prime(x):
    global count
    for d in range(2, x):
        count += 1
        if x % d == 0:
            return False
    return True


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


count = 0
print(next_prime(301), count)

Output:
307 22210

The biggest offender is computing all prime numbers betrween x and 2 * x. This version fixes that.

def is_prime(x):
    global count
    for d in range(2, x):
        count += 1
        if x % d == 0:
            return False
    return True


def next_prime(x):
    for n in range(x + 1, x * 2):
        if is_prime(n):
            return n


count = 0
print(next_prime(301), count)

Output:
307 314

22210 -> 314 is quite an improvement, but we can do better. This version of is_prime doesn't test factors that are multiples of 2 or are greater than the square root of x.

def is_prime(x):
    global count
    count += 1
    if x % 2 == 0:
        return False
    for d in range(3, int(x**0.5) + 1, 2):
        count += 1
        if x % d == 0:
            return False
    return True


def next_prime(x):
    for n in range(x + 1, x * 2):
        if is_prime(n):
            return n


count = 0
print(next_prime(301), count)

Output:
307 17

22210 -> 17.
Cleaned up it still isn't as pretty as your code, but it is hundreds of times faster.

def is_prime(x):
    return all(x % d for d in range(3, int(x**0.5) + 1), 2) if x % 2 else False


def next_prime(x):
    for n in range(x + 1, x * 2):
        if is_prime(n):
            return n

[Pedroski55]

Maths is definitely not my thing, but I tried like this:

Apart from 2, all prime numbers are odd.
Numbers ending in 0 or 5 are divisible by 5.
Numbers whose cross-sum is divisible by 3 are divisible by 3
11 is a strange number with weird properties, but that's another story!

A function to find prime numbers. I never played with prime numbers before, I hope this works!

def isPrime(anum):
    noP = {'0', '2', '4', '5', '6', '8'}
    P = {1, 2, 3, 5, 7}
    word = str(anum)
    if anum in P:
        #print(anum, 'is a prime number ... ')
        return True
    elif word[-1] in noP:
        #print(anum, 'is not a prime number.')
        return False
    sum_num = 0
    for w in word:
        sum_num = sum_num + int(w)
    if sum_num % 3 == 0:
        #print('The sum of', anum, 'is divisible by 3 so', anum, 'is not a prime number.')
        return False
    others = {7, 9}
    for n in others:
        if anum % n == 0:
            #print(anum, ' is divisible by', n, 'is not a prime number.')
            return False
    print('Can not find a factor for', anum, 'so it must be prime ... ')
    return True

You can get prime numbers using this:

for num in range(3, 2004, 2):
    if isPrime(num):
        print('*****************')
        print('The next prime number is', num)
        print('*****************')

For a given number, find the next prime number:

start = int(input('Enter a number ... '))
if not isPrime(start + 1):
    count = 1
    while not isPrime(start+ count):
        isPrime(start + count)
        count +=1
else:
    print('The next prime number is', start + count)

Check if a number is prime:

for n in range(1,2004):
    if 2003 % n == 0:
        print(n)

But I don't know if this uses too much time!

[DeaD_EyE]

sympy has an implementation in pure python with some math tricks.
You can find them here: https://github.com/sympy/sympy/blob/b7a7...14-L522C14

[deanhystad]

For fun I used ideas from the sympy prime code referenced by DeaD_EyE and re-ran some comparisons based on the algorithms in my previous post. This is my modified is_prime code that uses a small list of known primes (range 2 to 199).

def is_prime(x):
    global count
    if x in small_primes:
        return True
    nmax = int(x**0.5) + 1
    for n in small_primes:
        count += 1
        if n > nmax:
            return True
        if x % n == 0:
            return False
    for n in range(211, nmax, 2):
        count += 1
        if x % n == 0:
            return False
    return True

The next prime after 10067 is 10069. To calculate this the algorithm posted by FirstBornAlbatross performs 15,733,439 modulo divisions. The algorithm above performs 27.

The next prime after 100,000 is 100,003. Calculating all primes between 100,001 and 200,000 in a less than efficient manner performed 1,256,391,701 modulo divisions as opposed to 104 by the algorithm above. On my laptop the runtime was 150 seconds vs too small to measure.

And the inefficiency isn't all due to searching for all primes between x+1 and 2x. I ran a test to compute the next prime for every number in the range 100,001 and 200,000. Using the list of small primes to reduce how many factors are used to test for "primeness", my algorithm only hand to perform 18,000,463 modulo divisions. That looks like a lot, but 18 million is pretty small when compared to 1.25 billion.

[Pedroski55]

Apart from 2 and 5, all prime numbers end in 1, 3, 7, or 9

So all you need to look at are those numbers.

Then, looking for factors of a number, the smallest possible factor is really 3, and the largest factor will be 1/3 of the number.

So if you start dividing by 3 and work up by odd numbers to 1/3 * number, if you don't find any factors, the number must be prime, I think.

Something like this below: nextPrime(num) calls checkPrime(anum) until checkPrime(anum) returns True:

def checkPrime(anum):
    word = str(anum)        
    # numbers ending in 0 or 5 can't be prime numbers no matter how big
    if word[-1] in {'0', '5'}:            
        return False
    # speed things up at the beginning
    P = [2, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31,
         33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61,
         63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91,
         93, 97, 99, 103, 107, 109, 111, 113, 117, 119,
         121, 123, 127, 129, 131, 133, 137, 139, 141, 143,
         147, 149, 151, 153, 157, 159, 161, 163, 167, 169,
         171, 173, 177, 179, 181, 183, 187, 189, 191, 193,
         197, 199]
    if anum in P:
        #print(anum, 'is a prime number ... ')
        return True
    print('Looking for a prime number. Number is', anum)
    test = int((1/3) * anum)
    print('test is', test)
    # even numbers can't be prime so only check odd numbers
    if test % 2 == 0:
        test = test + 1
        print('test is', test)
    for n in range(3, test, 2):        
        # look for a factor, if found return False
        if anum % n == 0:           
            print(anum, 'divided by', n, ' = ', anum/n)
            print('Found a factor for', anum, 'which is', n, 'so', anum, 'is not a prime number')                
            return False
        else:                
            return True

def nextPrime(start):
    print('Check for the next prime number following', start)
    evens = {'0', '2', '4', '6', '8'}
    odds = {'1', '3', '5', '7', '9'}
    word = str(start)
    original = start
    # make start an odd number if it is even
    # could be the next number is a prime number
    if word[-1] in evens:        
        start = start + 1        
        count = 0
    # if start is odd, the next prime number must be at least start + 2
    if word[-1] in odds:
        count = 2
    # a prime number must be an odd number so increase by 2 each time looking for prime numbers
    while not checkPrime(start + count):
        count += 2
    print('After', original, 'the next prime number is', start + count)

To confirm that a result from checkPrime(anum) is actually a prime number, you can do this:

def isPrime(num):
    for i in range(1, num + 1):
        if num % i == 0:
            print('Found a factor for', num, 'which is', i)
            break

I get this kind of output:

Output:
nextPrime(1100)
Check for the next prime number following 1100
Looking for a prime number. Number is 1101
test is 367
1101 divided by 3  =  367.0
Found a factor for 1101 which is 3 so 1101 is not a prime number
Looking for a prime number. Number is 1103
test is 367
After 1100 the next prime number is 1103

[deanhystad]

I added Pedroski55's heuristic to is_prime().

def is_prime(x):
    # Check if x in small primes or in range of small primes
    if x in small_primes:
        return True
    if x < small_primes[-1]:
        return False

    # Check if x ends in digit that is divisible by 2 or 5
    if x % 10 not in (1, 3, 7, 9):
        return False

    # All non-prime numbers have a prime factor.  Check if
    # any of the small primes are a factor of x.
    nmax = int(x**0.5) + 1
    for n in small_primes:
        if n > nmax:
            return True
        if x % n == 0:
            return False

    # Brute force it the rest of the way.
    for n in range(211, nmax, 2):
        if x % n == 0:
            return False
    return True

I was surprised to find that this actually increases the number of modulo divisions by 10% I had to run the tests several times using different approaches to convince myself that this was true. I suppose that there are so many numbers not divisible by 2 or 5 that testing these numbers twice is inefficient.

I removed 2 and 5 from the list of small primes to prevent them being tested twice and repeated my tests. Now Pedroski55's heuristic is a 5% improvement over using the complete set of small primes.