fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bitset<1000001> bs;
  5. vector<long long> primes;
  6. long long gcd(long long a, long long b) {
  7. 	if (a < b) return gcd(b, a);
  8. 	if (b == 0) return a;
  9. 	return gcd(b, a % b);
  10. }
  11. void sieve()
  12. {
  13.     bs.set();
  14.     bs[0] = bs[1] = 0;
  15.     for(int p=2; p*p<=1000000; p++)
  16.     {
  17.         if(bs[p])
  18.         {
  19.         primes.push_back(p);
  20.             for(int i=p*p; i<=1000000; i+=p)
  21.                bs[i] = 0;
  22.         }
  23.     }
  24. }
  25.  
  26. int main()
  27. {
  28.     cin.tie(0);
  29.     cin.sync_with_stdio(0);
  30.  
  31.     long long a,b,ans=1;
  32.     cin >> a >> b;
  33.     a = gcd(a,b);
  34.     sieve();
  35.       for(long long i:primes)
  36.     {
  37.         if (a%i == 0) ans++;
  38.         while(a%i==0)
  39.             a /= i;
  40.     }
  41.     if(a!=1) ans++;
  42.  
  43. 	cout << ans;
  44.     return 0;
  45. }
  46.  
  47.  
  48.  
  49.  
Success #stdin #stdout 0.01s 5464KB
comments (?)
stdin
copy 
12 18
stdout
copy 
3
https://ideone.com/nm42lb
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!