#C13723. Prime Filtering
Prime Filtering
Prime Filtering
You are given a list of integers. Your task is to filter out the prime numbers from the list. A number \(n\) is prime if it is greater than 1 and has no positive divisors other than 1 and itself. You need to implement two functions:
is_prime(n): Determines if \(n\) is a prime number.filter_primes(int_list): Returns a new list containing only the prime numbers from the original list, preserving their order.
The input is given from standard input and the output must be printed to standard output.
Note: Use the following \(O(\sqrt{n})\) algorithm to check for primes:
\[
\text{if } n \le 1, \text{ return false}\\
\text{if } n \le 3, \text{ return true}\\
\text{if } n \bmod 2 = 0 \text{ or } n \bmod 3 = 0, \text{ return false}\\
\text{for } i = 5 \text{ to } \sqrt{n} \text{ with step }6 \text{ if } n \bmod i = 0 \text{ or } n \bmod (i+2) = 0 \text{ then return false}\\
\text{Otherwise, return true}
\]
inputFormat
The first line contains an integer \(n\) which represents the number of elements in the list. The second line contains \(n\) space-separated integers.
outputFormat
Print the prime numbers in the list in the same order as they appear in the input. If there are no prime numbers, print nothing. The numbers should be separated by a single space.
## sample6
2 3 4 5 9 11
2 3 5 11