fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using u64  = uint64_t;
  5. using u128 = unsigned __int128;
  6.  
  7. static constexpr u64 bases[] = 
  8. {2ULL, 325ULL, 9375ULL, 28178ULL,450775ULL, 9780504ULL, 1795265022ULL};
  9.  
  10. static constexpr u64 small_primes[] = 
  11. {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL};
  12.  
  13. // u64 mulmod(u64 a, u64 b, u64 mod){
  14. //     return (u128)a*b %mod; 
  15. // }
  16.  
  17. u64 modpow(u64 base, u64 expo, u64 mod){
  18.     u64 res = 1;
  19.     base %= mod;
  20.     while(expo){
  21.        if(expo&1) res = (u128)res*base %mod;
  22.        base = (u128)base*base %mod;
  23.        expo >>= 1;
  24.     }
  25. return res;
  26. }
  27.  
  28. bool isComposite(u64 a, u64 d, int s, u64 n){
  29.  
  30.     u64 x = modpow(a, d, n);
  31.     if(x==1 || x==n-1) return false;
  32.  
  33.     for(int r=1; r<s; r++){
  34.        x = (u128)x*x %n;
  35.        if(x==n-1) return false;
  36.     }
  37. return true;
  38. }
  39.  
  40. bool isPrime(u64 n){
  41.  
  42.     if(n<2) return false;
  43.  
  44.     for(u64 p : small_primes){
  45.        if(n==p) return true;
  46.        if(n%p==0) return false;
  47.     }
  48.  
  49.     u64 d = n-1;
  50.     int s = __builtin_ctzll(d);
  51.     d >>= s;
  52.  
  53.     for(u64 a : bases){
  54.        if(a%n==0) continue;
  55.        if(isComposite(a, d, s, n)) return false;
  56.     }
  57. return true;
  58. }
  59.  
  60. int main(){
  61.  
  62.     int t; cin >> t;
  63.  
  64.     while(t--){
  65.     long long n; cin >> n;
  66.     cout << (isPrime(n) ? "YES\n" : "NO\n");
  67.     }
  68.  
  69. return 0;    
  70. }
  71.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
1
101
stdout
copy 
YES
https://ideone.com/t6RKCI
language:
C++ (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!