HDU-2824-The Euler function(欧拉函数)

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int MAXN = 3000005;
LL euler[MAXN];
void init() {
    for (int i = 2; i < MAXN; i++) {
        euler[i] = i;
    }
    for (int i = 2; i < MAXN; i++) {
        if (euler[i] == i) {
            for (int j = i; j < MAXN; j += i) {
                euler[j] = euler[j] / i * (i - 1);
            }
        }
    }
    for (int i = 2; i < MAXN; i++) {
        euler[i] += euler[i - 1];
    }
}
int main() {
    init();
    int a,b;
    while (~scanf("%d%d",&a,&b)) {
        printf("%lldn",euler[b] - euler[a - 1]);
    }
    return 0;
} 

int euler(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }    
    }
    if (n != 1) {
        ans = ans / n * (n - 1);
    }
    return ans;
}