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

Related Topics: array, time-complexity

Description

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 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. The second line: \(n\) integers within range [0,100000].

Output Format

All the primes in original order.

Sample Input

5
3 4 5 6 7

Sample Output

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.