hdu 2824 The Euler function（歐拉函數）

The Euler function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3004    Accepted Submission(s): 1230

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
        

Source 2009 Multi-University Training Contest 1 - Host by TJU  

Recommend gaojie

題意：求那個式子啊.. 題解：先把歐拉函數的表用篩素數的方法搞出來

#include<stdio.h>
#include<string.h>
#define inf 3000000
long long f[inf+5];
void div()
{
    int i,j;
    memset(f,0,sizeof(f));
    f[0]=0;  f[1]=1;
    for(i=2; i<=inf; i++)
    {
        if(!f[i])
        {
            for(j=i; j<=inf; j+=i)
            {
                if(!f[j]) f[j]=j;
                f[j]=f[j]/i*(i-1);
            }
        }
        f[i]+=f[i-1];
    }
}
int main()
{
    int a,b;

    div();
    while(scanf("%d%d",&a,&b)>0)
    {
        if(a>b) a^=b^=a^=b;
        printf("%I64d\n",f[b]-f[a-1]);
    }

    return 0;
}