The Euler function（欧拉函数）

The Euler function

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 39 Accepted Submission(s) : 19

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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<stdio.h>
 2 #include<string.h>
 3 const int MAXN= 3000010;
 4 __int64 dp[MAXN];
 5 int main(){
 6     memset(dp,0,sizeof(dp));
 7     dp[1]=1;
 8     for(int i=2;i<MAXN;i++){
 9         if(dp[i])continue;
10         for(int j=i;j<MAXN;j+=i){
11             if(!dp[j])dp[j]=j;
12             dp[j]=dp[j]/i*(i-1);
13         }
14     }
15     for(int i=2;i<MAXN;i++)dp[i]+=dp[i-1];
16     int a,b;
17     while(~scanf("%d%d",&a,&b))printf("%I64d
",dp[b]-dp[a-1]);
18         return 0;
19 }

java超内存：

package com.lanqiao.week1;

import java.util.Scanner;

public class hdu2824 {
    private static Scanner cin = null;
    private static int MAXN = 3000010;
    static Long[] d = new Long[MAXN];
    static{
        cin = new Scanner(System.in);
        
    }
    
    public static void main(String[] args) {
        int a, b;
        for(int i = 1; i < MAXN; i++){
            d[i] = 0L;
        }
        for(int i = 2; i < MAXN; i++){
            if(d[i] == 0){
                for(int j = i; j < MAXN; j += i){
                    if(d[j] == 0)
                        d[j] = 1L * j;
                    d[j] = d[j] / i * (i - 1);
                }
            }
        }
        for(int i = 2; i < MAXN; i++){
            d[i] += d[i - 1];
        }
        while(cin.hasNext()){
            a = cin.nextInt();
            b = cin.nextInt();
            System.out.println(d[b] - d[a - 1]);
        }
    }
}