オイラー関数の評価

int Oula(int x)
{
    int i,res=x;
    for(i=2;i<(int)sqrt(x*1.0)+1;i++)

        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)
            x/=i;
        }
        if(x>1)
        res=res/x*(x-1);
        return res;
}

#define nmax 3000010
#define nnum 290000
int flag[nmax], prime[nnum];
int plen;
void mkprime(){
    int i,j;
    memset(flag,-1,sizeof(flag));
    for(i = 2, plen = 0; i < nmax; i ++){
        if(flag[i])
            prime[plen ++] = i;
        for(j = 0; (j < plen) && (i * prime[j] < nmax); j ++){
            flag[ i * prime[j] ] = 0;
            if(i % prime[j] == 0)
                break;
        }
    }
}
LL Oula(LL n) {//       
    int i, te;
    LL phi;
    te = (int) sqrt(n * 1.0);
    for (i = 0, phi = n; (i < plen) && (prime[i] <= te); i++) {
        if (n % prime[i] == 0) {
            phi = phi / prime[i] * (prime[i] - 1);
            while (n % prime[i] == 0) {
                n /= prime[i];
            }
        }
    }
    if (n > 1) {
        phi = phi / n * (n - 1);
    }
    return phi;
}

オーラ関数をすばやく求める:

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

#define bint __int64
#define N 3000001

bint phi[N];

void init()
{
    int i, j;
    for(i = 1; i < N; i++)
        phi[i] = i;

    for(i = 2; i < N; i++)
        if(i == phi[i]) //  i   
            for(j = i; j < N; j += i)  //j  i
                phi[j] = (phi[j] / i) * (i - 1); //j   i,  i   ,      
}

int main()
{
    init();
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF)
    {
        bint ans = 0;
        for(int i = a; i <= b; i++)
            ans += phi[i];
        printf("%I64d
", ans);
    }
    return 0;
}

数論では,正の整数nに対して,Euler関数はnに等しい数の中でnと相互作用する数より少ない数である.たとえばφ(8)=4,1,3,5,7はいずれも8と互質であるからである.Euler関数のアルゴリズム:一.1からN-1まで一つ一つ判断するときにEuler関数の条件を満たし、満足すれば概要を出力し、Euler関数&(N);二.オーラ関数と彼自身の異なる素因数の関係を利用して、PはNの素因数である.オーラ関数とそれ自体の異なる因数の関係:一般式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1−1/pn)p 1,p 2......pnはxのすべての素因数であり、xは0でない整数である.φ(1)=1(一意と1の互質の数は1そのものである).(注意:各素因数は1つしかありません.例えば12=2*2*3三.オーラ関数&(N)とNの標準的な非解釈の関係を利用してオーラ関数を解く.N=p 1^q 1*p 2^q 2*…pn^qnの場合&(N)=p 1^(q 1-1)*p 2^(q 2-1)…pn^(qn-1)*(p 1-1)*(p 2-1)*(p 3-1)…(pn-1)例えば234=2^1*3^2*13^1;則&(234)=2^(1-1)*3^(2-1)*13^(1-1)*(2-1)*(3-1)*(13-1);Euler関数のいくつかの推論1.Euler関数の数値は偶数2である.任意の素数pに対して&(p)=p-1がある.三.Nを指数Pの二乗、すなわちN=P*Pとすると&(N)=(P-POY)*P;四.このNは指数Pのn次方(n>=2)であり、&(N)=N*(1-1/P)である.