C++ – 欧拉函数

题目链接

部分代码

const int maxn=3e6;
long long euler[maxn+2];
void phi()
{
    for(int i=1;i<=maxn;i++)
    {
        euler[i]=i;
    }
    for(int i=2;i<=maxn;i++)
    {
        if(euler[i]==i)
        {
            for(int j=i;j<=maxn;j+=i)
            {
                euler[j]=euler[j]/i*(i-1);
            }
        }
        euler[i]+=euler[i-1];
    }
}

全部代码

#include<iostream>
using namespace std;
const int maxn=3e6;
long long euler[maxn+2];
void phi()
{
    for(int i=1;i<=maxn;i++)
    {
        euler[i]=i;
    }
    for(int i=2;i<=maxn;i++)
    {
        if(euler[i]==i)
        {
            for(int j=i;j<=maxn;j+=i)
            {
                euler[j]=euler[j]/i*(i-1);
            }
        }
        euler[i]+=euler[i-1];
    }
}
int main()
{
    int l,r;
    phi();
    while(cin>>l>>r)
    {
        cout<<euler[r]-euler[l-1]<<endl;
    }
    return 0;
}