题目大意：给一个正整数n，求出在[1, n]区间内和n互质的正整数的个数。Euler's Totient（欧拉函数）的直接应用。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef vector
          
            vi; 7 typedef long long ll; 8 #define MAXN 10000000 9 10 bitset
           
             bs;11 vi primes;12 13 void sieve(ll upper)14 {15 bs.set();16 bs.set(0, false);17 bs.set(1, false);18 for (ll i = 2; i <= upper; i++)19 {20 if (bs.test((size_t)i))21 for (ll j = i*i; j <= upper; j++)22 bs.set((size_t)j, false);23 primes.push_back((int)i);24 }25 }26 27 vi primeFactors(ll n)28 {29 vi factors;30 int idx = 0, pf = primes[idx];31 while (n != 1 && (pf*pf <= n))32 {33 while (n % pf == 0)34 {35 n /= pf;36 factors.push_back(pf);37 }38 pf = primes[++idx];39 }40 if (n != 1) factors.push_back(n);41 return factors;42 }43 44 int main()45 {46 #ifdef LOCAL47 freopen("in", "r", stdin);48 #endif49 sieve(MAXN);50 int n;51 while (scanf("%d", &n) && n)52 {53 vi factors = primeFactors(n);54 vi::iterator last = unique(factors.begin(), factors.end());55 int result = n;56 for (vi::iterator it = factors.begin(); it != last; it++)57 result = result - result/(*it);58 printf("%d\n", result);59 }60 return 0;61 }