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

 

题解:

求一个欧拉函数的和,求法参见.

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 using namespace std; 8 typedef long long ll; 9 const int N=3000005,M=300005;10 bool d[N];int l,r,phi[N],prime[M],m=0;11 void work(){12 int tmp;13 phi[1]=1;14 for(int i=2;i