Abstract Algebra: Theory and Applications

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\text{.}$ Begin by eliminating all of the multiples of $2\text{.}$ Next eliminate all of the multiples of $3\text{.}$ Now eliminate all of the multiples of $5\text{.}$ 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\text{;}$ it suffices to stop at $\sqrt{N}\text{.}$ Using this method, compute all of the prime numbers less than $N=250\text{.}$ We can also use this method to find all of the integers that are relatively prime to an integer $N\text{.}$ 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\text{.}$ Using the Sieve of Eratosthenes, write a program that will compute all of the primes less than an integer $N\text{.}$