366 http://inventwithpython.com/hacking
Email questions to the author: [email protected]
49 ÷ 7 = 7 remainder 0Actually, you only need to divide the number by prime numbers. For example, there’s no reason
to see if 6 divides 49, because if it did then 2 would have divided 49 since 2 is a factor of 6. Any
number that 6 divides evenly can also be divided by 2 evenly:
Figure 23-1. 2 divides 6, and 6 divides X, therefore 2 divides X.Because there’s an integer (that is not 1 or 49) that evenly divides 49 (that is, has a remainder of
0), we know that 49 is not a prime number. For another example, let’s try 13:
13 ÷ 2 = 6 remainder 113 ÷ 3 = 4 remainder 113 ÷ 4 = 3 remainder 1No integer divides 13 with a remainder of 0 (except for 1 and 13, which don’t count). Actually,
we don’t even have to divide all the numbers up to 13. We only have to test the integers up to
(and including) the square root of the number we are testing for primality. The square root of a
number is the number that is multiplied by itself to get that first number. The square root of 25 is
5, because 5 × 5 = 25. The square root of 13 is about 3.6055512754639, because
3.6055512754639 × 3.6055512754639 = 13. This means that when we were testing 13 for
primality, we only had to divide 2 and 3 because 4 is larger than the square root of 13.
Line 18 checks if the remainder of division is 0 by using the % mod operator. If line 17’s for
loop never returns False, the function will return True on line 20.
The Sieve of Eratosthenes
The sieve of Eratosthenes (pronounced “era, taws, thuh, knees”) is an algorithm for calculating
prime numbers. Imagine a bunch of boxes for each integer, all marked “prime”: