Prime Number Extraction

Given a list of integers, extract and print all the prime numbers in the order they appear in the input. A number \(n\) is considered prime if it satisfies \(n>1\) and has no divisors other than 1 and itself. To improve efficiency, you may use trial division up to \(\sqrt{n}\) and skip unnecessary checks such as even numbers and multiples of 3 after the initial cases.

Your program should read input from stdin and output the result to stdout.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\), representing the number of integers in the list.
• The second line contains \(n\) space-separated integers.

outputFormat

Output the extracted prime numbers separated by a single space on one line. If no prime numbers exist, output nothing.

9
2 3 4 5 6 7 8 9 10

2 3 5 7