*HDU 1286，2824欧拉函数

//1286
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
int main()
{
    int t,n,sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=n;
        for(int i=2;i<=sqrt(n);i++)
        {
            if(n%i==0)
            {
                sum=sum/i*(i-1);
                while(n%i==0)
                n/=i;
            }
        }
        if(n>1)
        sum=sum/n*(n-1);
     printf("%d
",sum);
    }
    return 0;
}
//2824
#include<cstdio>
#include<cstring>
#define size 3000001
int euler[size];
void Init()
{
    memset(euler,0,sizeof(euler));
    euler[1]=1;
    for(int i=2; i<size; i++)
        if(!euler[i])
            for(int j=i; j<size; j+=i)
            {
                if(!euler[j])
                    euler[j]=j;
                euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
            }
}
int main()
{
    int a,b;
    Init();
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        long long ans=0;
        for(int i=a;i<=b;i++)
        ans+=euler[i];
        printf("%lld
",ans);
    }
    return 0;
}
/*******************************************************/
模板：
(1)直接求小于或等于n,且与n互质的个数:
int Euler(int n)
{
    int ret=n;
    for(int i=2;i<=sqrt(n);i++)
    if(n%i==0)
    {
        ret=ret/i*(i-1);//先进行除法防止溢出(ret=ret*(1-1/p(i)))
        while(n%i==0)
        n/=i;
    }
    if(n>1)
    ret=ret/n*(n-1);
    return ret;
}
/********************************************************/
筛选模板:求[1,n]之间每个数的质因数的个数
#define size 1000001
int euler[size];
void Init()
{
    memset(euler,0,sizeof(euler));
    euler[1]=1;
    for(int i=2;i<size;i++)
    if(!euler[i])
    for(int j=i;j<size;j+=i)
    {
        if(!euler[j])
        euler[j]=j;
        euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
    }
}
/*****************************************************/
//比上面更快的方法
#include<cstdio>
using namespace std;
const int N = 1e6+10 ;
int phi[N], prime[N];
int tot;//tot计数，表示prime[N]中有多少质数 
void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            phi[i] = i-1;
            prime[tot ++] = i;
        }
        for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
}
 
int main(){
    Euler();
}