Guest User

Untitled

a guest
Jan 30th, 2020
145
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. std::vector <int> prime;
  2. bool is_composite[MAXN];
  3. int phi[MAXN];
  4.  
  5. void sieve (int n) {
  6.     std::fill (is_composite, is_composite + n, false);
  7.     phi[1] = 1;
  8.     for (int i = 2; i < n; ++i) {
  9.         if (!is_composite[i]) {
  10.             prime.push_back (i);
  11.             phi[i] = i - 1;                 //i is prime
  12.         }
  13.         for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
  14.             is_composite[i * prime[j]] = true;
  15.             if (i % prime[j] == 0) {
  16.                 phi[i * prime[j]] = phi[i] * prime[j];  //prime[j] divides i
  17.                 break;
  18.             } else {
  19.                 phi[i * prime[j]] = phi[i] * phi[prime[j]]; //prime[j] does not divide i
  20.             }
  21.         }
  22.     }
  23. }
RAW Paste Data