Advertisement
Araf_12

NOD

Mar 16th, 2021 (edited)
23
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | Source Code | 0 0
  1. const int MX = 1e6+123;
  2. bitset<MX> is_prime;
  3. vector<int> prime;
  4.  
  5. void primeGen ( int n )
  6. {
  7.     n += 100;
  8.     for ( int i = 3; i <= n; i += 2 ) is_prime[i] = 1;
  9.  
  10.     int sq = sqrt ( n );
  11.     for ( int i = 3; i <= sq; i += 2 ) {
  12.         if ( is_prime[i] == 1 ) {
  13.             for ( int j = i*i; j <= n; j += ( i + i ) ) {
  14.                 is_prime[j] = 0;
  15.             }
  16.         }
  17.     }
  18.  
  19.     is_prime[2] = 1;
  20.     prime.push_back (2);
  21.  
  22.     for ( int i = 3; i <= n; i += 2 ) {
  23.         if ( is_prime[i] == 1 ) prime.push_back ( i );
  24.     }
  25. }
  26.  
  27.  
  28. int NOD (long long n) // 60
  29. {
  30.     int ret = 1;
  31.     for ( auto p : prime ) { // p = 5
  32.         if ( 1LL * p * p > n ) break;
  33.  
  34.         if ( n % p == 0 ) {
  35.             int cnt = 1;
  36.  
  37.             while ( n % p == 0 ) { // n = 5
  38.                 n /= p; // n = 5;
  39.                 cnt++; // 2
  40.             }
  41.  
  42.             ret *= cnt; // 1 * 3 * 2
  43.         }
  44.     }
  45.  
  46.     if ( n > 1 ) ret *= 2; // 1 * 3 * 2  * 2 = 12
  47.  
  48.     return ret;
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement