Solved Problem - Check Prime

In this lesson, we'll look at an efficient way to perform the primality test.

Problem statement

Given a number, NN, check if it’s prime or not. Do this for TT test cases.

Input format

The first line contains a positive integer TT (1T103)(1 \leq T \leq 10^3).

The following TT lines contain a positive integer NN (2N108)(2 \leq N \leq 10^8).

Output format For each integer, NN, print yes if NN is prime, otherwise print no on a new line.


Sample

Input

5
34 
29 
11 
14 
6

Output

no 
yes 
yes 
no 
no

Brute force

The brute force solution would be to check whether N has any factor between 22 and N1N-1 (inclusive).

The time complexity would be O(N)O(N) for one test case. So the overall time complexity would be O(TN)O(T*N).


Optimization

Similar to the factorization problem. We only need to iterate up to N\sqrt{N} to find factors.

This reduces our time complexity to O(TN)O(T*\sqrt{N}), which is good enough for given the constraints.

Get hands-on with 1200+ tech skills courses.