Abstract Algebra: Theory and Applications · Problem 2.5.1

Groups — Thomas Judson

Mathematics — Abstract Algebra · sieve-of-eratosthenes

Problem

The Sieve of Eratosthenes. One method of computing all of the prime numbers less than a certain fixed positive integer

N

is to list all of the numbers

n

such that

1 < n < N

. Begin by eliminating all of the multiples of

2

. Next eliminate all of the multiples of

3

. Now eliminate all of the multiples of

5

. Notice that

4

has already been crossed out. Continue in this manner, noticing that we do not have to go all the way to

N

; it suffices to stop at

\sqrt{N}

. Using this method, compute all of the prime numbers less than

N = 250

. We can also use this method to find all of the integers that are relatively prime to an integer

N

. Simply eliminate the prime factors of

N

and all of their multiples. Using this method, find all of the numbers that are relatively prime to

N = 120

. Using the Sieve of Eratosthenes, write a program that will compute all of the primes less than an integer

N