HDU 2824 The Euler function 欧拉φ函数：φ(n)是所有小于n的正整数里，和n互素的整数的个数。n是一个正整数。 欧拉证明了下面这个式子： 如果n的标准素因子分解式是p1^a1p2^a2……pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 如果n为奇素数，φ(n)=n-1. 解法：线性筛选法 在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素) (1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)a; (2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

#include<stdio.h>
#include<stdlib.h>
__int64  num[3000024];
int prime[220000];
bool isprime[3000024]={0};
void eular()
{
    int count=0;
    __int64 k;
    for( int i=2; i<=3000000; i++ )
    {       
        if( !isprime[i] )
        {
            prime[++count]=i;
            num[i]=i-1;
        }
        for( int j=1; j<=count&&( (k=prime[j]*i)<=3000000 );j++  )
        {
            isprime[k]=1;
            if( i%prime[j]==0 )
            {
                num[k]=num[i]*prime[j];
            }
            else num[k]=num[i]*( prime[j]-1 );
        }
    }
}
int main( )
{
    int n,m,i;
    eular();//结果存储在num[]中
    for(i = 3;i <=3000000;i++)
        num[i] = num[i-1] + num[i];
    while( scanf( "%d%d",&n,&m )!=EOF )
        printf( "%I64d\n",num[m]-num[n-1] );
    return 0;
}