Primality Test

 For a given number N check if it is prime or not. A prime number is a number which is only divisible by 1 and itself.

Example 1:

Input:
N = 5
Output: Yes
Explanation: 5 is a prime number.

Example 2:

Input:
N = 4
Output: No
Explanation: 4 is not a prime number.

Your Task:
You don't need to read input or print anything. Your task is to complete the function isPrime() that takes N as parameter and returns True if N is prime else returns false. 

Expected Time Complexity : O(N1/2)
Expected Auxilliary Space :  O(1)

Constraints:
1 <= N <= 109     

The link of this problem is  https://practice.geeksforgeeks.org/problems/primality-test/1

Solution:

Python3

import math

def isPrime(N):

    if N<2:

        return False

    for i in range(2,int(math.sqrt(N))+1):

        if N%i==0:

            return False

    return True

def main():

    T=int(input())

    while(T>0):

        N=int(input())

        if(isPrime(N)):

            print("Yes")

        else:

            print("No")

        T-=1

if __name__=="__main__":

    main()