Separate Prime and Non-Prime Numbers

Given a list of integers, your task is to separate the prime numbers from the non-prime numbers. A number ( n ) is considered prime if it satisfies ( n > 1 ) and has no divisors other than ( 1 ) and itself. In other words, if ( n \le 1 ) it is not prime, and if ( n = 2 ) or ( n = 3 ) it is prime. For numbers greater than 3, if ( n ) is divisible by 2 or 3, it is not prime; otherwise, check divisibility from 5 up to ( \sqrt{n} ) with a step pattern of 6. The program should read the input from standard input and output the list of prime numbers and non-prime numbers on two separate lines, preserving the order from the input.

inputFormat

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

outputFormat

The output contains two lines. The first line lists all prime numbers in the order they appear (space-separated). The second line lists all non-prime numbers (space-separated). If a list is empty, output an empty line for that list.## sample

0