You cannot submit for this problem because the homework's deadline is due.

Problem: Zed brags that he can immediately point out all prime numbers from a sequence of integers. You don't believe that so you are going to write a program to check. Given a sequence of integers within a certain range, you need to find out all the prime numbers without changing their order. Recall that a prime number is a natural number greater than 1 divisible only by itself and 1.

Requirement: To check if an integer is a prime, intuitively we can achieve that by dividing integers smaller than itself. However, there is a more efficient algorithm called Eratosthenes Sieve, and you are required to implement it for this exercise. The algorithm works as follows:

1. For all integers within a given range, mark them as prime
2. For 0 and 1, mark them as not prime
3. Find the next smallest integer i that is marked as prime
4. For all integers that can be divided by i, mark them as not prime
5. Repeat Steps 3-4 until no more i can be found in Step 3

After running the above algorithm, you have generated a lookup table. To check if a given integer is a prime, simply check that lookup table and see if it is marked as prime or not.

Input Format: The first line: an integer n (1 <= n <= 20) that stands for the length of the sequence in the second line. The second line: n integers within the range [0,100000].

# sample
5
3 4 5 6 7

Output Format: All the primes in the original order.

# sample
3 5 7

Takeaway: In this exercise, we used more space to store the lookup table, but thanks to that we can solve the problem in less time. Time-space Tradeoff is very common when you try to solve problems and hope this exercise gives you a basic sense.

Tags: #array #time-complexity