Prime Filter Using Sieve of Eratosthenes

You are given a list of non-negative integers. Your task is to filter out the prime numbers from the list and output them in the same order as they appear in the list.

To determine whether a number is prime, first generate a list of prime numbers up to the maximum value in the list using the Sieve of Eratosthenes algorithm. The algorithm is based on the concept that all non‐prime numbers can be marked as multiples of some prime number.

The Sieve of Eratosthenes is defined as follows in \( \LaTeX \):

\[ \text{sieve}(n) = \left\{ p \in \mathbb{N} : 2 \leq p \leq n \wedge p \text{ is prime} \right\} \]

Then, filter the given list by checking if each number exists in the prime set.

If the input list is empty or contains no prime numbers, output an empty string.

inputFormat

The first line of input contains an integer \( n \) denoting the number of elements in the array. The second line contains \( n \) space-separated non-negative integers.

outputFormat

Output the prime numbers from the list, separated by a single space. If there are no prime numbers, output an empty line.

5
2 4 7 11 9

2 7 11