Sort Primes in Array

You are given an array of n integers. Your task is to rearrange the prime numbers present in the array in ascending order while keeping the non-prime numbers in their original positions.

A number \(p\) is considered prime if \(p > 1\) and it has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, etc. are prime numbers. Non-prime numbers (including 1, 0, and negative numbers) must remain at their original positions.

For instance, given the input array [10, 29, 11, 4, 5], the output should be [10, 5, 11, 4, 29] because we sort the primes (29, 11, 5) into (5, 11, 29) while leaving non-prime numbers unchanged.

inputFormat

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

outputFormat

Output the modified array as a single line of space-separated integers after arranging the prime numbers in ascending order while keeping non-prime numbers at their original positions.

5
10 29 11 4 5

10 5 11 4 29