Prime Number Extraction Using the Sieve of Eratosthenes

This problem requires you to extract prime numbers from a given list using the Sieve of Eratosthenes algorithm.

You are given a list of integers. Your task is to filter out the prime numbers from the list while keeping the original order. To solve this problem, first compute all primes up to the maximum number in the input list using the Sieve of Eratosthenes. Then, use the precomputed information to determine which numbers in the list are primes.

Recall that the Sieve of Eratosthenes algorithm can be summarized by the formula:

$$\text{For } n \ge 2, \; S = \{2,3,\ldots,n\} \quad \text{and mark multiples of each prime } p \text{ starting from } p^2.$$</p>

If no prime is found, output an empty line.

## inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer n indicating the number of elements in the list.
• The second line contains n space-separated integers.

## outputFormat

Output the extracted prime numbers in the order they appear in the list on a single line, separated by a single space. If there are no prime numbers, output an empty line.

## sample

8
10 15 20 23 29 31 45 50

23 29 31

$$