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?