Chapter 23 – Finding Prime Numbers 363The above number is so big, I’m going to guess you didn’t even read it to notice the typo in it.
Composite Numbers.................................................................................................................................................
Integers that are not prime numbers are called composite numbers, because they are composed
of at least two factors besides 1 and the number itself. They are called composite numbers
because these number are composed of prime numbers multiplied together, such as the composite
number 1,386 being composed of the prime numbers in 2 × 3 × 3 × 7 × 11.
Here are four facts about prime numbers:
- Prime numbers are integers greater than 1that have only 1 and themselves as factors.
- Two is the only even prime number. (Though I guess that makes two a very odd
prime number.) - There are an infinite number of prime numbers. There is no “largest prime number”.
- Multiplying two prime numbers will give a number that only has two pairs of
factors, 1 and itself (like all numbers do), and the two prime numbers that were
multiplied. For example, 3 and 7 are prime numbers. 3 times 7 is 21. The only
factors for 21 are 1, 21, 3, and 7.
Source Code for The Prime Sieve Module
First we will create a module that has functions related to prime numbers:
isPrime() will return either True or False if the number passed to it is prime or not. It will
use the “divides test” algorithm.
primeSieve() will use the “Sieve of Eratosthenes” algorithm (explained later) to generate
numbers.
Like cryptomath.py, the primeSieve.py program is only meant to be imported as a module to our
other programs. It does not do anything when run on its own.
Open a new file editor window by clicking on File ► New Window. Type in the following code
into the file editor, and then save it as primeSieve.py.
Source code for primeSieve.py
Prime Number Sieve
http://inventwithpython.com/hacking (BSD Licensed)
- import math
- def isPrime(num):