题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2824
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)

Input

There are several test cases. Each line has two integers a, b (2<a<b<3000000).

Output

Output the result of (a)+ (a+1)+....+ (b)

Sample Input

3 100

Sample Output

3042

Problem solving report:

Description: (n)表示小于等于n与n互质的个数，求(a)+(a + 1)+ .... +(b)
Problem solving: 欧拉函数打表。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000005;
int eul[MAXN + 5];
void Euler() {
    for (int i = 1; i < MAXN; i++)
        eul[i] = i;
    for (int i = 2; i < MAXN; i++) {
        if (eul[i] == i)
            for (int j = i; j < MAXN; j += i)
                eul[j] = eul[j] / i * (i - 1);
    }
}
int main() {
    Euler();
    int l, r;
    while (~scanf("%d%d", &l, &r)) {
        long long ans = 0;
        for (int i = l; i <= r; i++)
            ans += eul[i];
        printf("%lld\n", ans);
    }
    return 0;
}