## Description

In this assignment you will write a Python program that reads a positive integer n from user input, then

prints out the first n prime numbers. An integer m is said to be divisible by another (non-zero) integer d if

and only if there exists an integer k such that

m k d . Equivalently m is divisible by d if and only if the

remainder of m upon (integer) division by d is zero. In this case we say that d is a divisor of m. A positive

integer p is called prime if its only positive divisors are 1 and p. The one exception to this rule is the number

1 itself, which is considered to be non-prime. A positive integer that is not prime is called composite.

Euclid showed that there are infinitely many prime numbers. The prime and composite sequences begin as

follows:

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, …

There are many ways to test a number m for primality, but perhaps the simplest is to do a sequence of trial

divisions. Begin by dividing m by 2. If it divides evenly (i.e. has zero remainder), then m is not prime,

otherwise divide by 3. Continue in this fashion dividing by 4, then 5, etc. If at any point m is found to be

divisible by a number d in the range

2 d m1, then halt, and conclude that m is composite. Otherwise,

conclude that m is prime. However a moment’s thought shows that one need only do trial divisions by

numbers that are themselves prime. For instance if a trial division by 2 fails (i.e. has non-zero remainder

showing that m is odd), then a trial division by 4, 6, 8 or any even number must also fail. Therefore to test

a number m for primality do trial divisions by prime numbers less than m.

A little more thought shows that it is not necessary to go all the way up to

m1

, and in fact one need only

divide m by primes p in the range

2 p m . To see this, suppose

m 1

is composite. Then there exist

positive integers a and b such that

1 a m, 1b m

, and

m ab

. If both

a m

and

b m

, then

m m m a b m

, a contradiction. Hence either

a m

or

b m

, and it follows that some prime

satisfying

2 p m

divides m. Therefore if no such prime exists, then m must itself be prime.

Your goal in this project is to implement this process in Python. You will write a function called

isPrime() with the heading

def isPrime(m, L):

where m is the number to be tested for primality and L is a list containing sufficiently many primes to do

the testing. This function will return True or False according to whether m is prime or composite. At the

time isPrime(m, L) is called, the list L must contain (at least) all primes p in the range

2 p m . For

instance to test

m 53

for primality, one does successive trial divisions by 2, 3, 5 and 7. We go no further

since

11 53

. Thus when isPrime(53, L) is called we must have

len(L) 4

and

L[0] 2 , L[1] 3,

L[2] 5 , L[3] 7

. The return value in this case would be true since all these divisions fail. Similarly to

test

m143

divide by 2, 3, 5, 7 and 11 (since

13 143

). Thus when isPrime(143, L) is called it

must be that

len(L) 5

and

L[0] 2 , L[1] 3, L[2] 5 , L[3] 7 , L[4] 11

. The return is false in this

case since 11 divides 143. Function isPrime() will contain a loop that steps through the list L doing

2

trial divisions, terminating when either a trial division succeeds (in which case false is returned), or when

the next prime in L is greater than

m

(in which case true is returned.)

The main program in this project (i.e. that part of the program outside of any function) will prompt for and

receive a positive integer giving the number of primes to generate. In the context of this main program we

will refer to the list of primes as PrimeList, though you may use any variable name you like. PrimeList

will contain only a small number of primes initially. Your main program will enter a loop that appends

new primes to PrimeList until it is of the required length, then print out the contents of the list in the

format described below. Observe that PrimeList plays a dual role in this project. On the one hand it is

used to collect, store and print the output data. On the other hand, it is passed to function isPrime() to

test new integers for primality. Whenever isPrime() returns true, the newly discovered prime is

appended to PrimeList. This process works since as explained above, the primes needed to test an integer

m range only up to

m

, and all of these primes (and more) will be stored in PrimeList at the time m is

tested. It is necessary to initialize PrimeList to hold at least one prime, say PrimeList = [2], or

PrimeList = [2, 3].

The following is an outline of the steps to be performed by the main program.

• Prompt for and read a positive integer n giving the number of primes to generate.

• Initialize PrimeList to store the first several primes in order.

• Enter a loop that calls function isPrime() on successive integers, appends newly discovered

primes to PrimeList, and halts when PrimeList is of the required length.

• Print the contents of PrimeList 10 to a line, separated by single spaces. Note that if n is not a

multiple of 10, then the last line of output will contain fewer than 10 primes.

Your program, which will be called Primes.py, will produce output matching the sample runs below. (As

usual % signifies the terminal prompt.)

% python Primes.py

Enter the number of Primes to compute: 10

The first 10 primes are:

2 3 5 7 11 13 17 19 23 29

% python Primes.py

Enter the number of Primes to compute: 97

The first 97 primes are:

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

3

% python Primes.py

Enter the number of Primes to compute: 285

The first 285 primes are:

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 653 659

661 673 677 683 691 701 709 719 727 733

739 743 751 757 761 769 773 787 797 809

811 821 823 827 829 839 853 857 859 863

877 881 883 887 907 911 919 929 937 941

947 953 967 971 977 983 991 997 1009 1013

1019 1021 1031 1033 1039 1049 1051 1061 1063 1069

1087 1091 1093 1097 1103 1109 1117 1123 1129 1151

1153 1163 1171 1181 1187 1193 1201 1213 1217 1223

1229 1231 1237 1249 1259 1277 1279 1283 1289 1291

1297 1301 1303 1307 1319 1321 1327 1361 1367 1373

1381 1399 1409 1423 1427 1429 1433 1439 1447 1451

1453 1459 1471 1481 1483 1487 1489 1493 1499 1511

1523 1531 1543 1549 1553 1559 1567 1571 1579 1583

1597 1601 1607 1609 1613 1619 1621 1627 1637 1657

1663 1667 1669 1693 1697 1699 1709 1721 1723 1733

1741 1747 1753 1759 1777 1783 1787 1789 1801 1811

1823 1831 1847 1861 1867

%

What to turn in

Submit the file Primes.py to the assignment name pa4 in the usual way. This project is somewhat more

complex than previous assignments, so get started early and ask questions if anything is less than clear.