The Euler function-蒲公英云

The Euler function

题目描述：

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

思路：就是求一个区间内的欧拉函数之和，

给出一个结论：

设E( x)为X的欧拉函数，p为质数

对于E（x*p）

if p是x的因数 E(x*p)=E(x)*p;

else E (x*P)=E(x)*(p-1);

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxv=3e6+10;
int v[3000005],a[3000006],b[3000005];//b数组就是欧拉函数
void init(){
    for(int i=2;i<3000006;i++){
        if(!v[i]){
            a[++a[0]]=i;
            b[i]=i-1; 
        }
        for(int j=1;j<=a[0]&&i*a[j]<3000006;j++){
            v[i*a[j]]=1;
            if(i%a[j]==0){
                b[i*a[j]]=b[i]*a[j];
                break;
            }else{
                b[i*a[j]]=b[i]*(a[j]-1);
            }
        }
    }
} 
int main(){
    int n,m,len;
    init();
    long long sum=0;
    cin>>n>>m;
    if(n>m)swap(n,m);
    for(int i=n;i<=m;i++)sum+=b[i];
    cout<<sum;
}