Algorithm

problem link- https://www.spoj.com/problems/PON/

PON - Prime or Not

#cryptography #prime-numbers-1 #primality-test

 

Given the number, you are to answer the question: "Is it prime?"

Solutions to this problem can be submitted in C, C++, Pascal, Perl, Python, Ruby, Lisp, Hask, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.

Input

t – the number of test cases, then t test cases follows. [t <= 500]
Each line contains one integer: N [2 <= N <= 2^63-1]

Output

For each test case output string "YES" if given number is prime and "NO" otherwise.

Example

Input:
5
2
3
4
5
6

Output:
YES
YES
NO
YES
NO

 

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <stdio.h>
int isPrime(long long n){
	if (n <= 1)  return 0;
	    if (n <= 3)  return 1;
	 
	    // This is checked so that we can skip 
	    // middle five numbers in below loop
	    if (n%2 == 0 || n%3 == 0) return 0;
	 
	    for (int i=5; i*i<=n; i=i+6)
	        if (n%i == 0 || n%(i+2) == 0)
	           return 0;
	 
	    return 1;
}
int main(void) {
	int t;
	scanf("%d", &t);
	while(t--){
		long long n;
		scanf("%lld", &n);
		if(isPrime(n))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
2
3
4
5
6

Output

x
–
+
cmd
YES
YES
NO
YES
NO

#2 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio&ft;
#include <cstdlib>

using namespace std;

typedef unsigned long long ULL;

ULL mulmod(ULL a, ULL b, ULL c){
	ULL x = 0,y = a%c;
	
	while(b>0){
		if(b&1) x = (x+y)%c;
		y = (y<<1)%c;
		b >>= 1;
	}
	
	return x;
}

ULL pow(ULL a, ULL b, ULL c){
	ULL x = 1, y = a;
	
	while(b>0){
		if(b&1) x = mulmod(x,y,c);
		y = mulmod(y,y,c);
		b >>= 1;
	}
	
	return x;
}

bool miller_rabin(ULL p, int it){
	if(p<2) return false;
	if(p==2) return true;
	if((p&1)==0) return false;
	
	ULL s = p-1;
	while(s%2==0) s >>= 1;
	
	while(it--){
		ULL a = rand()%(p-1)+1,temp = s;
		ULL mod = pow(a,temp,p);
		
		if(mod==-1 || mod==1) continue;
		
		while(temp!=p-1 && mod!=p-1){
			mod = mulmod(mod,mod,p);
			temp <<= 1;
		}
		
		if(mod!=p-1) return false;
	}
	
	return true;
}

int main(){
	int T;
	unsigned long long N;
	scanf("%d",&T);
	
	while(T--){
		scanf("%llu",&N);
		printf("%s\n",miller_rabin(N,18)? "YES" : "NO");
	}
	
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
2
3
4
5
6

Output

x
–
+
cmd
YES
YES
NO
YES
NO
Advertisements

Demonstration

SPOJ Solution-Prime or Not-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python