Trying to find the next prime number - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Trying to find the next prime number (/thread-40506.html) |
Trying to find the next prime number - FirstBornAlbratross - Aug-08-2023 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? RE: Trying to find the next prime number - deanhystad - Aug-08-2023 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. RE: Trying to find the next prime number - FirstBornAlbratross - Aug-09-2023 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)}") RE: Trying to find the next prime number - deanhystad - Aug-10-2023 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) 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) 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) 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 RE: Trying to find the next prime number - Pedroski55 - Aug-11-2023 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 TrueYou 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! RE: Trying to find the next prime number - DeaD_EyE - Aug-11-2023 sympy has an implementation in pure python with some math tricks.You can find them here: https://github.com/sympy/sympy/blob/b7a7ee1b7096486d8ecd460332506e04033cce13/sympy/ntheory/primetest.py#L522C14-L522C14 RE: Trying to find the next prime number - deanhystad - Aug-11-2023 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 TrueThe 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. RE: Trying to find the next prime number - Pedroski55 - Aug-14-2023 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) breakI get this kind of output:
RE: Trying to find the next prime number - deanhystad - Aug-14-2023 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 TrueI 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. |