2014
02-17

# The Euler function

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)

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

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

3 100

3042

#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;
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。