# PROBLEM LINK:

https://www.codechef.com/NITJ2021/problems/CIN002

* Author:* Aayush Varshney

*Aayush Varshney*

**Tester:***Aayush Varshney*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Prime Sieve

# PROBLEM:

**Supermarket Dilemma**

Chef is going to local supermarket but there appears a problem with chef as he is confused about which Supermarket he can choose to go as he is not able to decide whether he can park his car in that particular supermarket’s parking lot or not! There are **N** parking slots in each supermarket which are marked from **1,2,3,4…N**.

Chef will go to that supermarket in which he gets to know that there is exactly **1** empty parking slot having number K that exactly divides the total number of slots **(N)** available in that supermarket.

The **1st** and **Nth** parking slots are always occupied by the staff of every supermarket. Rest parking slots are empty as Chef is arriving early morning to the supermarket.

Now Chef needs your help in determining whether he can park his car in a supermarket or not!

**Input**

The first line contains the single integer **N** showing how many supermarkets are there for the chef to choose.

The next **N** lines contain a number **‘ai’** which represents the total parking slots available in **ith** supermarket.

**Output**

You need to output “**YES**” (without the quotes), if a supermarket can be reached by Chef, and “**NO**” (without the quotes), if it can’t.

**Constraints**

1<=N<=105

1<=ai<=1012

**Time Limit : 2 second(s)**

**Sample Input :**

2

4

5

**Sample Output :**

YES

NO

# QUICK EXPLANATION:

Since using loops to check if each number is prime would cause a TLE so we use a prime sieve.

# EXPLANATION:

The question wants us to find if a supermarket with n parking slots has exactly 3 divisors (1st and nth for staff and 1 for Chef himself).

We know that the prime numbers are the only numbers with 2 divisors (1 and the number itself).

So the number with exactly 3 divisors will be a square of prime numbers.

So one way can be to use Sieve of Eratosthenes and do precomputation for all test cases.

Then we can answer each test case in O(1).

# SOLUTIONS:

## Setter's Solution

// Coded by Aayush Varshney

#include<bits/stdc++.h>

#define ll long long

#define f(i,n) for(ll i=0;i<n;i++)

using namespace std;

ll isprime[1000000+5];

void sieve()

{

memset(isprime,1,sizeof(isprime));

isprime[0]=isprime[1]=0;

for(ll i=2;i*i<=1000000+5;i++)
{
if(isprime[i])
{
for(ll j=i*i;j<=1000000+5;j=j+i)

isprime[j]=0;

}

}

}

void testcase()

{

ll n;

cin>>n;

ll x=sqrt(n);

if(sqrt(n)==x)

{

if(isprime[x])

cout<<“YES”;

else

cout<<“NO”;

}

else

cout<<“NO”;

cout<<endl;

}

int main()

{

ios_base::sync_with_stdio(false); cin.tie(NULL);

ll t=1;

cin>>t;

sieve();

f(i,t)

{

// cout<<“Case #”<<i+1<<": ";

testcase();

}

return 0;

}

## Tester's Solution

// Coded by Aayush Varshney

#include<bits/stdc++.h>

#define ll long long

#define f(i,n) for(ll i=0;i<n;i++)

using namespace std;

ll isprime[1000000+5];

void sieve()

{

memset(isprime,1,sizeof(isprime));

isprime[0]=isprime[1]=0;

for(ll i=2;i*i<=1000000+5;i++)
{
if(isprime[i])
{
for(ll j=i*i;j<=1000000+5;j=j+i)

isprime[j]=0;

}

}

}

void testcase()

{

ll n;

cin>>n;

ll x=sqrt(n);

if(sqrt(n)==x)

{

if(isprime[x])

cout<<“YES”;

else

cout<<“NO”;

}

else

cout<<“NO”;

cout<<endl;

}

int main()

{

ios_base::sync_with_stdio(false); cin.tie(NULL);

ll t=1;

cin>>t;

sieve();

f(i,t)

{

// cout<<“Case #”<<i+1<<": ";

testcase();

}

return 0;

}

## Editorialist's Solution

// Coded by Aayush Varshney

#include<bits/stdc++.h>

#define ll long long

#define f(i,n) for(ll i=0;i<n;i++)

using namespace std;

ll isprime[1000000+5];

void sieve()

{

memset(isprime,1,sizeof(isprime));

isprime[0]=isprime[1]=0;

for(ll i=2;i*i<=1000000+5;i++)
{
if(isprime[i])
{
for(ll j=i*i;j<=1000000+5;j=j+i)

isprime[j]=0;

}

}

}

void testcase()

{

ll n;

cin>>n;

ll x=sqrt(n);

if(sqrt(n)==x)

{

if(isprime[x])

cout<<“YES”;

else

cout<<“NO”;

}

else

cout<<“NO”;

cout<<endl;

}

int main()

{

ios_base::sync_with_stdio(false); cin.tie(NULL);

ll t=1;

cin>>t;

sieve();

f(i,t)

{

// cout<<“Case #”<<i+1<<": ";

testcase();

}

return 0;

}