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[] = {2ULL,3ULL,5ULL,7ULL,11ULL,13U,17ULL};
  11.  
  12. static inline u64 mulmod(u64 a, u64 b, u64 mod){
  13.     return (u128)a*b %mod;
  14. }
  15.  
  16. static inline u64 modpow(u64 base, u64 expo, u64 mod){
  17.     u64 res = 1;
  18.     base %= mod;
  19.     while(expo){
  20.         if(expo&1) res = mulmod(res, base, mod);
  21.         base = mulmod(base, base, mod);
  22.         expo >>= 1;
  23.     }
  24.     return res;
  25. }
  26.  
  27. static inline bool isComposite(u64 a, u64 d, int s, u64 n){
  28.     u64 x = modpow(a, d, n);
  29.     if(x==1 || x==n-1) return false;
  30.  
  31.     for(int r=1; r<s; r++){
  32.        x = mulmod(x, x, n);
  33.        if(x==n-1) return false;
  34.     }
  35.     return true;
  36. }
  37.  
  38. bool isPrime(u64 n){
  39.  
  40.     if(n<2) return false;
  41.  
  42.     for(u64 p : small_primes){
  43.        if(n==p) return true;
  44.        if(n%p==0) return false;
  45.     }
  46.  
  47.     u64 d = n-1;
  48.     int s = __builtin_ctzll(d);
  49.     d >>= s;
  50.  
  51.     for(u64 a : bases){
  52.        if(a%n==0) continue;
  53.        if(isComposite(a, d, s, n)) return false;
  54.     }
  55.     return true;
  56. }
  57.  
  58. int main(){
  59.     cout << (isPrime(561) ? "prime\n" : "not prime\n");
  60. }
  61.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
not prime
https://ideone.com/fvVAPM
language:
C++ (gcc 8.3)
created:
22 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!