Generating Prime Numbers
The Sieve of Eratosthenes is an elegant algorithm for finding all of the prime numbers up to some limit n. The basic idea is to first create a list of numbers from 2 to n. The first number is removed from the list, and announced as a prime number, and all multiples of the number up to n are removed from the list. This process continues until the list is empty.
For example, if we wished to find all the primes up to 10, the list would originally contain [2, 3, 4, 5, 6, 7, 8, 9, 10]. The 2 is removed and announced to be prime. Then 4, 6, 8, and 10 are removed, since they are multiples of 2. That leaves [3, 5, 7, 9]. Repeating the process, 3 is announced as prime, and 9 is removed because it is a multiple of 9. That leaves [5, 7]. And so on.
Write a program called generatePrimes.py that prompts the user for a number n and outputs all the primes less than or equal to n. You must use the algorithm described above.