(close)

Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

Prev: Powerball Lottery | Next: Progress Bar
Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

Prime Numbers

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.

- What error do you get if you change
`response.isdecimal()`

on line 22 to`response`

and enter a non-number for the number from which to start searching for primes? - What happens if you change
`number < 2`

on line 38 to`number > 2`

? - What happens if you change
`number % 1 == 0`

on line 46 to`number % i != 0`

?