ALGOQ007-Editorial

editorial
1

PROBLEM NAME:

PRIME

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

EASY

PREREQUISITES:

BASIC MATHS

Solution:

We know that all numbers above 4 can be expressed as the sum of other prime numbers so when the given number is less than 5 and is prime we will print “1 NO” and if it is greater than 4 and prime we will print “1 YES”.


#include <iostream>
#include <string>
#define ll long long int
using namespace std;
bool isPrime(ll n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
int main() {
int tc;
cin>>tc;
while(tc-->0){
   ll n;
   cin>>n;
   if(isPrime(n)){
       if(n==2||n==3){
           cout<<1<<" NO"<<"\n";
       }else{
           cout<<1<<" YES"<<"\n";
       }
   }else{
       cout<<0<<"\n";
   }
 
 
}
	return 0;
}