Euler's Phi Function(Sieve).cpp

TotientSieve.cpp

#define M 1000005
int phi[M]; // প্রতিটা ইনডেক্সে টশিয়ান্ট ভ্যালু রাখার জন্য array

void totientSieve() {
  for (int i = 1; i < M; i++) {
    phi[i] = i;
  }
  for (int p = 2; p < M; p++) {
    if (phi[p] == p) { // এখানে p প্রাইম নাম্বার 
      for (int k = p; k < M; k += p) {
        phi[k] -= phi[k] / p;
      }
    }
  }
}