欧拉函数

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

【题意】

给定区间a,b要求a到b的欧拉函数对应的值的和

直接上模板

#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>typedef long long ll;using namespace std;const int size=3000000;ll euler[size];void init(){    memset(euler,0,sizeof(euler));    euler[1]=1;    for(ll i=2;i<=size;i  )    {        if(euler[i]==0)        {            for(ll j=i;j<=size;j =i)            {                if(euler[j]==0)                {                    euler[j]=j;                }                euler[j]=euler[j]/i*(i-1);            }        }    }}int main(){    init();    ios::sync_with_stdio(false);    ll a,b;    while(cin>>a>>b)    {        ll sum=0;        for(ll i=a;i<=b;i  )            sum =euler[i];        cout<<sum<<endl;    }    return 0;}

后看到网上有人用前缀和做：

#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#define ll long longusing namespace std;const int size=3000000;ll euler[size 10];void init(){    memset(euler,0,sizeof(euler));    euler[1]=1;    for(ll i=2;i<=size;i  )    {        if(euler[i]==0)        {            for(ll j=i;j<=size;j =i)            {                if(euler[j]==0)                {                    euler[j]=j;                }                euler[j]=euler[j]/i*(i-1);                //先进行除法是为了防止中间数据的溢出            }        }    }    for(ll i=3;i<=size;i  )     //前缀和    {        euler[i] =euler[i-1];    }}int main(){    init();          //初始化，首先求出每个数对应的质因数个数    ll a,b;    while(~scanf("%lld%lld",&a,&b))    {        printf("%lld\n",euler[b]-euler[a-1]);    }    return 0;}