Use this link to get 70% off the Automate the Boring Stuff online video course.
Support me on Patreon
A prime number is a number that is evenly divisible only by one and itself. Prime numbers have a variety of practical applications, but no algorithm can predict them; we must calculate them one at a time. However, we do know that there is an infinite number of prime numbers to be discovered.
This program finds prime numbers through brute-force calculation. Its code is similar to Project 24, “Factor Finder.” (Another way to describe a prime number is that one and the number itself are its only factors.) You can find out more about prime numbers from https://en.wikipedia.org/wiki/Prime_number.
When you run primenumbers.py, the output will look like this:
Prime Numbers, by Al Sweigart [email protected]
--snip--
Enter a number to start searching for primes from:
(Try 0 or 1000000000000 (12 zeros) or another number.)
> 0
Press Ctrl-C at any time to quit. Press Enter to begin...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, --snip--The isPrime() function accepts an integer and returns True if it is a prime number. Otherwise, it returns False. Project 24 is worth studying if you’re trying to understand this program. The isPrime() function essentially looks for any factors in the given number and returns False if it finds any.
The algorithm in this program can quickly find large prime numbers. The number one trillion has a mere 10 digits. But to find prime numbers that are as big as a googol (a one followed by 100 zeros), you need to use an advanced algorithm such as the Rabin-Miller primality test. Chapter 22 of my book Cracking Codes with Python (No Starch Press, 2018) has a Python implementation of this algorithm.
1. """Prime Numbers, by Al Sweigart [email protected]
2. Calculates prime numbers, which are numbers that are only evenly
3. divisible by one and themselves. They are used in a variety of practical
4. applications.
5. More info at: https://en.wikipedia.org/wiki/Prime_number
6. This code is available at https://nostarch.com/big-book-small-python-programming
7. Tags: tiny, math, scrolling"""
8.
9. import math, sys
10.
11. def main():
12. print('Prime Numbers, by Al Sweigart [email protected]')
13. print('Prime numbers are numbers that are only evenly divisible by')
14. print('one and themselves. They are used in a variety of practical')
15. print('applications, but cannot be predicted. They must be')
16. print('calculated one at a time.')
17. print()
18. while True:
19. print('Enter a number to start searching for primes from:')
20. print('(Try 0 or 1000000000000 (12 zeros) or another number.)')
21. response = input('> ')
22. if response.isdecimal():
23. num = int(response)
24. break
25.
26. input('Press Ctrl-C at any time to quit. Press Enter to begin...')
27.
28. while True:
29. # Print out any prime numbers:
30. if isPrime(num):
31. print(str(num) + ', ', end='', flush=True)
32. num = num + 1 # Go to the next number.
33.
34.
35. def isPrime(number):
36. """Returns True if number is prime, otherwise returns False."""
37. # Handle special cases:
38. if number < 2:
39. return False
40. elif number == 2:
41. return True
42.
43. # Try to evenly divide number by all numbers from 2 up to number's
44. # square root.
45. for i in range(2, int(math.sqrt(number)) + 1):
46. if number % i == 0:
47. return False
48. return True
49.
50.
51. # If this program was run (instead of imported), run the game:
52. if __name__ == '__main__':
53. try:
54. main()
55. except KeyboardInterrupt:
56. sys.exit() # When Ctrl-C is pressed, end the program.
Try to find the answers to the following questions. Experiment with some modifications to the code and rerun the program to see what effect the changes have.
response.isdecimal() on line 22 to response and enter a non-number for the number from which to start searching for primes?number < 2 on line 38 to number > 2?number % 1 == 0 on line 46 to number % i != 0?