_Muhammad

Prime factorization

Oct 21st, 2020
704
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. vector<long long> factorize (long long n)
  29. {
  30.     vector<long long> ret;
  31.     for ( auto p : prime ) {
  32.         if ( 1LL * p * p > n ) break;
  33.  
  34.         if ( n % p == 0 ) {
  35.             ret.push_back (p);
  36.  
  37.             while ( n % p == 0 ) {
  38.                 n /= p;
  39.             }
  40.         }
  41.     }
  42.  
  43.     if ( n > 1 ) ret.push_back(n);
  44.  
  45.     return ret;
  46. }
  47.  
RAW Paste Data