题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2824

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
题意大概是：给两个数，求这两个数之间的数的欧拉函数值；

需要知道欧拉函数这个东西，引用一下百度百科的东西：

利用欧拉函数和它本身不同质因数的关系，用 筛法计算出某个范围内所有数的欧拉函数值。
欧拉函数和它本身不同质因数的关系：
欧拉函数ψ（N）=N{∏p|N}（1－1/p）
 
亦即:
   
（P是数N的 质因数）
如：
ψ（10）=10×（1－1/2）×（1－1/5）=4；
ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；
ψ（49）=49×（1－1/7）=
   
=42。 

#include<stdio.h>
#include<string.h>
#include<math.h>

#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define da    10000000
#define xiao -10000000
#define clean(a,b) memset(a,b,sizeof(a))
#define max 3000005

ll shuzu[max];

void eular()
{
    ll  ret=1;
	int i,j;
	shuzu[1]=0;
	for(i=2;i<max;++i)								//初始化为本身 
		shuzu[i]=i;
	for(i=2;i<max;++i)								
	{
		if(shuzu[i]==i)								//若没被处理过 
		{
			for(j=i;j<max;j=j+i)					
				shuzu[j]=shuzu[j]/i*(i-1);			//处理出所有的本身的值 
		}
	}
	for(i=2;i<max;++i)
		shuzu[i]=shuzu[i]+shuzu[i-1];				//后一项加前一项； 
}

int main ()
{
	eular();										//预处理所有范围内的值 
    int a,b;
    ll sum=0;
    while(~scanf("%d%d",&a,&b))
    {
	    int i,j;
		sum=shuzu[b]-shuzu[a-1];					//范围内的 注意减 
		printf("%lld\n",sum);
	}
}