fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector <int> prime_factorization(int n) {
  5.     vector <int> temp;
  6.  
  7.     for (int i = 2; i * 1LL * i<= n; ++i) {
  8.         while (n % i == 0) {
  9.             n /= i;
  10.             temp.push_back(i);
  11.         }
  12.     }
  13.    // cout << n << endl;
  14.    if (n > 1) temp.push_back(n);
  15.  
  16.     return temp;
  17. } // O( sqrt(n) )
  18.  
  19. const int N = 1e5 + 5;
  20. vector <bool> isPrime;
  21. vector <int> primes;
  22.  
  23. void sieve() {
  24.     isPrime.assign(N + 1, true);
  25.     isPrime[0] = isPrime[1] = false;
  26.  
  27.     for (int i = 2; i * i < N; i++) {
  28.         if (!isPrime[i]) continue;
  29.  
  30.         for (int j = i * i; j < N; j += i) {
  31.             isPrime[j] = false;
  32.         }
  33.     }
  34.     for (int i = 2; i < N; ++i) {
  35.         if (isPrime[i]) {
  36.             primes.push_back(i);
  37.         }
  38.     }
  39. }
  40.  
  41.  
  42. vector <int> prime_fact(int n) {
  43.     vector <int> temp;
  44.     for (auto &x: primes) {
  45.         if ( x * x > n) break;
  46.         while (n % x == 0) {
  47.             n /= x;
  48.             temp.push_back(x);
  49.         }
  50.     }
  51.     if (n > 1) temp.push_back(n);
  52.     return temp;
  53. } // O ( sqrt(n) / ln (sqrt(n)) ) ~ O (sqrt(n) / ln (n))
  54. /// Prime number theorem: The number of primes less than or equal to n is approximately n / ln(n)
  55. /// So, the number of primes less than or equal to sqrt(n) is approximately sqrt(n) / ln(sqrt(n)) = sqrt(n) / ln(n)
  56.  
  57.  
  58. vector <pair<int,int>> prime_fact_pair(int n) {
  59.     vector <pair<int,int>> temp;
  60.     for (auto &x: primes) {
  61.         if ( x * x > n) break;
  62.         int cnt = 0;
  63.         while (n % x == 0) {
  64.             n /= x;
  65.             cnt++;
  66.         }
  67.         temp.push_back( {x, cnt} );
  68.     }
  69.     if (n > 1) temp.push_back( {n, 1} );
  70.     return temp;
  71. } // O ( sqrt(n) / ln (sqrt(n)) ) ~ O (sqrt(n) / ln (n))
  72.  
  73. long long bigPow(int b, int e)
  74. {
  75.     if (e == 0) return 1;
  76.     long long ret = bigPow(b, e / 2);
  77.     ret = ret * ret;
  78.     if (e & 1) ret = ret * b; 
  79.     return ret;
  80. }
  81.  
  82. int gcd(map<int,int> &mp1, map<int,int> &mp2) {
  83.     // vector<pair<int, int>> factors;
  84.  
  85.     // for (auto &x: mp1) {
  86.     //     if (mp2.count(x.first)) {
  87.     //         factors.push_back( {x.first, min(x.second, mp2[x.first])} );
  88.     //     }
  89.     // }
  90.  
  91.     // int res = 1;
  92.     // for (auto &x: factors) {
  93.     //     res *= bigPow(x.first, x.second);
  94.     //     // cout << x.first << " " << x.second << endl;
  95.     // }  
  96.  
  97.     int res = 1;
  98.     for (auto &x: mp1) {
  99.         if (mp2.count(x.first)) {
  100.             res *= pow(x.first, min(x.second, mp2[x.first]));
  101.         }
  102.     }
  103.     return res;
  104. }
  105.  
  106. int main() {
  107.     ios_base::sync_with_stdio(false), cin.tie(nullptr);
  108.  
  109.     sieve();
  110.  
  111.     auto vec1 = prime_fact(30);
  112.     auto vec2 = prime_fact(12);
  113.     map<int,int> mp1, mp2;
  114.     for (auto &x: vec1) mp1[x]++;
  115.     for (auto &x: vec2) mp2[x]++;
  116.     cout << gcd(mp1, mp2) << endl;
  117.  
  118.  
  119.     return 0;
  120.  
  121. }
  122.  
  123.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/K77x6s
language:
C++14 (clang 8.0)
created:
29 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!