Paste Search Dynamic
Recent pastes
Miller Rabin
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <vector>
  5. #include <algorithm>
  6. #define LL long long
  7. #define II __int128
  8. using namespace std;
  9.  
  10. namespace Miller_Rabin{
  11.         LL mul_(LL x, LL y, LL mod){
  12.                 return (II)x*y%mod;
  13.         }
  14.        
  15.         LL pow_(LL x, LL y, LL mod){
  16.                 LL res = 1;
  17.                 for(x %= mod; y; x = mul_(x, x, mod), y >>= 1){
  18.                         if(y&1) res = mul_(res, x, mod);
  19.                 }
  20.                 return res;
  21.         }
  22.        
  23.         bool miller_rabin(LL n, LL a){
  24.                 if(n <= 1) return false;
  25.                 if(n == 2) return true;
  26.                 if(n == a) return true;
  27.                
  28.                 for(LL d = n-1; true; d >>= 1){
  29.                         LL res = pow_(a, d, n);
  30.                         if(res == n-1) return true;
  31.                         if(d&1) return res == 1 || res == n-1;
  32.                 }
  33.         }
  34.        
  35.         bool is_prime(LL n){
  36.                 for(LL a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
  37.                         if(!miller_rabin(n, a)) return false;
  38.                 }
  39.                 return true;
  40.         }
  41. }
  42.  
  43. namespace Pollard_Rho{
  44.         LL gcd(LL a, LL b){
  45.                 return b ? gcd(b, a%b) : a;
  46.         }
  47.        
  48.         void dnc(LL n, vector<LL> &vc){
  49.                 if(n == 1) return;
  50.                 if(n%2 == 0){
  51.                         vc.push_back(2);
  52.                         dnc(n/2, vc);
  53.                         return;
  54.                 }
  55.                 if(Miller_Rabin::is_prime(n)){
  56.                         vc.push_back(n);
  57.                         return;
  58.                 }
  59.                
  60.                 LL a, b, c, g = 1;
  61.                 a = b = rand()%(n-2)+2;
  62.                 c = rand()%20+1;
  63.                 auto f = [&](LL x){
  64.                         return (c+Miller_Rabin::mul_(x, x, n))%n;
  65.                 };
  66.                 printf("%lld %lld %lld %lld %lldn", n, a, b, c, g);
  67.                 while(g == 1){
  68.                         a = f(a);
  69.                         b = f(f(b));
  70.                         g = gcd(abs(a-b), n);
  71.                         printf("%lld %lld %lld %lld %lldn", n, a, b, c, g);
  72.                 }
  73.                
  74.                 dnc(g, vc);
  75.                 dnc(n/g, vc);
  76.         }
  77.        
  78.         vector<LL> factorize(LL n){
  79.                 vector<LL> vc;
  80.                 dnc(n, vc);
  81.                 sort(vc.begin(), vc.end());
  82.                 return vc;
  83.         }
  84. };
  85.  
  86. int main(){
  87.         LL n;
  88.        
  89.         srand((unsigned int)time(null));
  90.        
  91.         scanf("%lld", &n);
  92.        
  93.         for(LL i = 1; i <= 100; i++){
  94.                 printf("%d", Miller_Rabin::is_prime(i));
  95.                 if(i%10 == 0) printf("n");
  96.         }
  97.         //for(LL p : Pollard_Rho::factorize(n)) printf("%lldn", p);
  98.        
  99.         return 0;
  100. }
Parsed in 0.009 seconds