Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Primality Test | Fermat
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull binpower(ull a, ull n1, ull n2){ ull res = 1; a%=n2; while(n1>0){ if(n1&1) res=(res*a)%n2; a=(a*a)%n2; n1>>=1; } return res%n2; } bool probablyPrimeFermat(ull n, int iter=20) { if (n < 4) return n == 2 || n == 3; for (int i = 0; i < iter; i++) { ull a = 2 + rand() % (n - 3); if (binpower(a, n - 1, n) != 1) return false; } return true; } int main(){ int t; cin>>t; while(t--){ ull n; cin>>n; if(probablyPrimeFermat(n)==1) cout<<"YES"; else cout<<"NO"; cout<<'\n'; } return 0; }
run
|
edit
|
history
|
help
0
Straight Max-Min
Perfect Square Solution
c++_array_size
czekolada
ListCPP
Test 12(2021)
Summation Of Primes
boost::shared_ptr<base>& arg
Cpp update 1
codechef