Run Code
|
API
|
Code Wall
|
Users
|
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
Please
log in
to post a comment.
Finding the first digit of a number
vem de livezada
mur1
Binary Tree
Prosta implementacja algorytmu Euklidesa (NWD)
Get all anagrams from given words
D.E.Shaw Binary Search Question
cppPyPoly2
cynb
Ploshtina na pravoagolnik
Please log in to post a comment.