Prime checking

Revision en1, by oversolver, 2017-09-07 17:14:58

Your given a simple task:

For given number 2 ≤ n ≤ 1018 check prime or not it is.

Limits are: 1 second TL, 16Mb ML.

And we have solution:

bool isprime(LL n){
	if(n<2) return false;
	for(LL i=2;i*i*i<=n;++i) if(n%i==0) return false;
	for(int it=0;it<1e5;++it){
		LL i = rand()%(n-1)+1;
		if(__gcd(i,n)!=1) return false;
		if(mpow(i,n-1,n)!=1) return false;
	}
	return true;
}

where rand() returns 64-bit random integer and mpow(a,b,m) is ab modulo m.

Can you challenge this solution?

Tags primes, prime numbers

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English oversolver 2017-09-07 17:14:58 563 Initial revision (published)