Prime Numbers

Tags: tiny, math, scrolling

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.

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.

prime_numbers.py
 1"""Prime Numbers, by Al Sweigart al@inventwithpython.com
 2Calculates prime numbers, which are numbers that are only evenly
 3divisible by one and themselves. They are used in a variety of practical
 4applications.
 5More info at: https://en.wikipedia.org/wiki/Prime_number
 6This code is available at https://nostarch.com/big-book-small-python-programming
 7Tags: tiny, math, scrolling"""
 8
 9import math, sys
10
11def main():
12    print('Prime Numbers, by Al Sweigart al@inventwithpython.com')
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
35def 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:
52if __name__ == '__main__':
53    try:
54        main()
55    except KeyboardInterrupt:
56        sys.exit()  # When Ctrl-C is pressed, end the program.

https://inventwithpython.com/bigbookpython/project56.html