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
te lo paso
Kadane's Algorithm
Exempel 2
binary
stack
KMP substring search
mergeSort
runtime template mode processor
Vector+-OpLoad
combine c++ string with dynamically allocated c array of chars through overloaded add operator