fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6.  
  7. ull mul_mod(ull a, ull b, ull mod) {
  8.     return (__uint128_t)a * b % mod;
  9. }
  10.  
  11. ull pow_mod(ull a, ull d, ull mod) {
  12.     ull result = 1;
  13.     a %= mod;
  14.     while (d) {
  15.         if (d & 1) result = mul_mod(result, a, mod);
  16.         a = mul_mod(a, a, mod);
  17.         d >>= 1;
  18.     }
  19.     return result;
  20. }
  21.  
  22. bool is_prime_mr(ull n) {
  23.     if (n < 2) return false;
  24.     if (n == 2 || n == 3) return true;
  25.     if (n % 2 == 0) return false;
  26.  
  27.     ull d = n - 1;
  28.     int s = 0;
  29.     while ((d & 1) == 0) {
  30.         d >>= 1;
  31.         s++;
  32.     }
  33.  
  34.     vector<ull> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  35.     for (ull a : bases) {
  36.         if (a >= n) continue;
  37.         ull x = pow_mod(a, d, n);
  38.         if (x == 1 || x == n - 1) continue;
  39.         bool composite = true;
  40.         for (int r = 1; r < s; r++) {
  41.             x = mul_mod(x, x, n);
  42.             if (x == n - 1) {
  43.                 composite = false;
  44.                 break;
  45.             }
  46.         }
  47.         if (composite) return false;
  48.     }
  49.     return true;
  50. }
  51.  
  52. ull f(ull x, ull c, ull mod) {
  53.     return (mul_mod(x, x, mod) + c) % mod;
  54. }
  55.  
  56. ull pollard_rho(ull n) {
  57.     if (n % 2 == 0) return 2;
  58.     ull x = rand() % (n - 2) + 2;
  59.     ull y = x;
  60.     ull c = rand() % (n - 1) + 1;
  61.     ull d = 1;
  62.     while (d == 1) {
  63.         x = f(x, c, n);
  64.         y = f(f(y, c, n), c, n);
  65.         d = __gcd((x > y ? x - y : y - x), n);
  66.     }
  67.     if (d == n) return pollard_rho(n);
  68.     return d;
  69. }
  70.  
  71. ull find_smallest_prime_factor(ull n) {
  72.     if (is_prime_mr(n)) return n;
  73.     ull factor = pollard_rho(n);
  74.     while (!is_prime_mr(factor)) {
  75.         factor = pollard_rho(factor);
  76.     }
  77.     return factor;
  78. }
  79.  
  80. int main() {
  81.     ios::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.     srand(time(0));
  84.  
  85.     ull N;
  86.     cin >> N;
  87.  
  88.     if (N < 4) {
  89.         cout << 0 << endl;
  90.         return 0;
  91.     }
  92.  
  93.     ull p = find_smallest_prime_factor(N);
  94.     ull q = N / p;
  95.  
  96.     if (is_prime_mr(p) && is_prime_mr(q)) {
  97.         if (p == q) {
  98.             cout << 1 << endl;
  99.         } else {
  100.             cout << 2 << endl;
  101.         }
  102.     } else {
  103.         cout << 0 << endl;
  104.     }
  105.  
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/GYm9am
language:
C++14 (gcc 8.3)
created:
5 days 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!