All Tracks Math Number Theory Primality Tests Problem

Shootout in London
Tag(s):

Easy, Math, Sieve

Problem
Editorial
Analytics

There is a major shootout going on in London. Gunmen can be encountered in most of the streets and only a few of them are safe. Sherlock is given the responsibility to ensure the safety of the people by asking them to shift to the nearest safe street.
There are $$N$$ streets on the road. The $$i^{th}$$ street is denoted by the number $$A[i]$$. Gunmen do not enter streets that are denoted by a prime number i.e. $$i^{th}$$ street is safe, if $$A[i]$$ is a prime.

Help Sherlock find the nearest safe street for people trapped in all the $$N$$ streets i.e. print $$N$$ integers, where the $$i^{th}$$ integer is the index (1-based) of the nearest safe street. The distance between cities $$i$$ and $$j$$ is given by $$|i-j|$$. For any city $$j$$, if there exists no safe city $$i$$, such that people of city $$j$$ can move to city $$i$$, print $$-1$$ for it.

Note :

-If there are multiple nearest safe streets, print the one with the lower index.

Input:

The first line contains a single integer $$N$$ denoting the number of cities. The next line contains $$N$$ integers, where the $$i^{th}$$ integer denotes $$A[i]$$ .

Output:
Print the answer on a single line.

Constraints:

$$ 1 \le N \le 5 \times 10^5 $$

$$ 1 \le A[i] \le 10^6 $$

SAMPLE INPUT
5
1 2 3 1 6
SAMPLE OUTPUT
2 2 3 3 3
Explanation

.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications