The Euler function
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6018 Accepted Submission(s): 2539

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

3000000的数据范围，没想到是直接加的......贡献一次MLE。

#include <stdio.h>#include <string.h>int euler[3000010];void Euler_Sieve_Method(int * euler, int n) {    euler[1] = 1;    for (int i = 2; i < n; i++) {        euler[i] = i;    }    for (int i = 2; i < n; i++) {        if (euler[i] == i) {            for (int j = i; j < n; j += i) {                euler[j] = euler[j] / i * (i - 1);            }        }    }}int main() {    Euler_Sieve_Method(euler, 3000005);    int a, b;    while (scanf("%d%d", &a, &b) != EOF) {        __int64 s = 0;        for (int i = a; i <= b; i++) {            s += euler[i];        }        printf("%I64d\n", s);    }    return 0;}

View Code

The Euler function[HDU2824]