Sort Primes First

Your task is to write a program that processes a list of integers and reorders them so that all prime numbers appear before all non-prime numbers. The relative order of the prime numbers and that of the non-prime numbers must remain the same as in the original list.

A prime number is defined as a natural number greater than 1 that has no divisors other than 1 and itself. Use \(\LaTeX\) for any mathematical formulas. For example, a number \(n\) is prime if and only if \(n>1\) and for every integer \(d\) such that \(2 \le d \le \sqrt{n}\), \(d\) does not divide \(n\) evenly.

The program should read input from standard input (STDIN) and output the result to standard output (STDOUT).

inputFormat

The first line of input contains a single integer \(N\) representing the number of elements in the list. The second line contains \(N\) space-separated integers.

outputFormat

Output a single line containing the rearranged list where all prime numbers appear first (in the same order as they appear in the input) followed by the non-prime numbers (also preserving their original order). The numbers should be separated by a single space.

6
11 4 3 15 7 10

11 3 7 4 15 10