オイラー関数、オイラーふるい

オイラー関数 | オイラー篩#

概要#

オイラー関数 $\phi_i$$(phi_i)$ は $<=i$ かつ $i$ と互いに素な数の個数を表します。非完全積性関数です。

オイラー篩は線形篩の一種です。時間計算量は $O (UpperLimit)$ です。線形に積性関数を求めるために使用できます。

原理#

オイラー篩#

オイラー篩は現在の素数 $i$ と以前の素数 $Primes_1 \sim Primes_{cnt}$ を掛け合わせ、それらを篩い落とします。オイラー篩は各合成数がその最小の素因子によって篩い落とされることを保証します。

その核心コードはif(i % Primes[j] == 0) break;であり、この文はオイラー篩の時間計算量が線形であることを保証します。

証明：$i\mod Primes_j == 0$ のとき、2 つの可能性があります：

$ i $ が素数である場合。この場合、$i$（$Primes_j == i$）がすでに捕捉され、$i^2$ が篩い落とされます。明らかに、素数 $i$ に対して、$i^2$ の最小の素因子は $i$ です。
$i$ が合成数である場合。この場合、$Primes_j$ が $i$ の最小の素因子であることを示しています。したがって、$i * Primes_j$ の素因子は $Primes_j$ と $i$ の素因子です。明らかに、$Primes_j < i$ なので、$Primes_j$ は現在までの $i * Primes_j$ の最小の素因子です。しかし、$ Primes $ 配列は単調増加であり、その後篩い落とされる各 $iPrimes_{j’}$ の最小の素因子はもはや $Primes_{j’}$ ではなく、前の $Primes_j$ です（前の $i \mod Primes_j == 0$ なので、$Primes_j$ は $i$ の最小の素因子であり、$iPrimes_j$ の最小の素因子でもあります）。したがって、各合成数がその最小の素因子によって篩い落とされることを保証できなくなります。したがってBreakです。

さらに、$UpperLimit$ 以内の各合成数は篩い落とされます。明らかに、$UpperLimit$ 以内の各数は $UpperLimit$ 以内の素因子を持っています。

オイラー関数#

$\phi_i$ の一般的な表現式：$\phi_i = i * \prod_{j=1}^{cnt_i}(1-\frac {1}{p_j} )$ 、容積原理を使用します：

$i$ を素因数分解し、$i=\prod_{j=1}^{cnt} p_i^{e_i}$ を得ます。$p$ は $i$ の素因子です。したがって、$<i$ の $p_j$ の任意の倍数は $i$ と互いに素ではありません。これらの数の個数は $ \frac {n}{p_1} + \frac {n}{p_2} + ... \frac {n}{p_j}$ です。$n$ からこれらの数を引きます。当然、いくつかの重複する場合もあります。つまり、$\frac {n}{p_1p_2}$ のようなものを加え戻す必要があります。この式を容積原理を使って整理すると、$\phi_i = i * \prod_{j=1}^{cnt}(1-\frac {1}{p_i} )$ が得られます。

$\phi$ にはいくつかの特別な性質があります。$\phi_i$ を考えます：

明らかに、$i$ が素数であるとき、$\phi_i=i-1$ です。
$i$ が $p^k$ の形で書ける場合、ここで $p$ は素数です。したがって、$\phi_i = p^k - p^{k-1}$ です。

? 証明：$p^k$ を考えます。$\phi_{p^k}$ の中の数は $p$ を因子に持たない必要があります。直接計算するのは難しいので、逆に計算します。$p^k$ 内に $p$ を因子に持つ数は $ p,2p,3p,4p, \ldots,pp,(p+1)*p,\ldots,(p^{k-1}-1)*p,p^{k-1}*p$ であり、合計 $p^{k-1}$ 個です。
$i$ が $mn$ の形で書ける場合、ここで $m,n$ は互いに素です。したがって、$\phi_i = \phi_{m}\phi_{n}$ です。すなわち、オイラー関数の部分積性です。

? 証明：$m$ と $n$ が互いに素であることは、$m$ と $n$ が同じ素因子を持たないことを示しています。したがって、彼らの唯一分解式は完全に異なります。すなわち、$m = \prod_{j=1}^{cnt_m} p_j^{e_j}$、$n=\prod_{j=1}^{cnt_n} p_j^{e_j}$ です。したがって、$\phi_m = m*\prod_{j=1}^{cnt_m}(1-\frac {1}{p_j})$、$\phi_n = n*\prod_{j=1}^{cnt_n}(1-\frac {1}{p_j})$ です。唯一分解式が完全に異なるため、明らかに $\phi_{mn} = \phi_m\phi_n$ です。

$\phi$ の定義と $\phi$ の性質に基づいて、$\phi_i$ の再帰的な求め方を考えます：

$i$ が素数の場合、$\phi_i=i-1$ です。
$i$ が素数でない場合：

$i = x * p$ とします。ここで $p$ は素数です。
- $p$ が $x$ の因子である場合、したがって $\phi_i=p*\phi_x$ です。
  
  ? 証明：この証明は少し面倒です。$\phi_x$ の中の任意の要素を $a$ とします。まず、次の証明に役立つ事実を示します：
  
  ? ・$a$ が $x$ と互いに素である場合、$a$ は $x*p$ と互いに素である必要があります（$p$ は前述の素数です）。
  
  ? 次に、$a$ が $x$ と互いに素であるとき、$a+x$ も $x$ と互いに素であることを証明する必要があります。明らかに、$a,x$ が互いに素であることは $\Leftrightarrow gcd (a,x) =1$ です。したがって、証明すべきことは $gcd (a+x,x)=1$ です。反証法を用いることができます：（もちろん、これはより相減損術です）
  
  ? 仮定 $gcd (a+x,x)=b$（ここで $b \neq 1$）。さらに、$a+x = k_1b,x=k_2b$ とします。したがって、$a=(k_1-k_2)*b$ です。明らかに、$gcd ((k_1-k_2)b,k_2b) = b$ なので、$gcd (a,x)>=b$ です。
  
  ? この証明が何の役に立つかというと、$\phi_i=p*\phi_x$ を証明したいのです。上記の結論が得られたので、$\phi_x$ 集合内の各要素 $a$ が $i$ と互いに素であることがわかります。$i=xp$ なので、$x$ 内の $a,a+x,a+2x,\ldots,a+(p-1)x$ はすべて $i$ と互いに素です。このような $a$ は $\phi_x$ 個あります。各 $a$ は $i$ と互いに素な数に $p$ 個拡張できます。この時、$\phi_i=p\phi_x$ が証明されます。
- $p$ が $x$ の因子でない場合、したがって $\phi_i=(p-1)*\phi_x$ です。
  
  ? 証明：明らかにこの場合 $p$ は $x$ と互いに素であり、$\phi_i = \phi_x * \phi_p$ です。また、$\phi_p = p-1$ であることが知られているので、$\phi_i=(p-1)*\phi_x$ が明らかです。

実装#

#define rep(x,y,z) for(int x=y,I=z;x<=z;++x)
inline void Euler_Sieve(){
    rep(i,2,lim){
        if(!isprime[i]) primes[++prime]=i,phi[i]=i-1;
        for(int j=1;i*primes[j]<=lim;j++){
            phi[i*primes[j]]=phi[i]*(primes[j]-1),isprime[i*primes[j]]=true;
            if(i%primes[j]==0) { phi[i*primes[j]]=phi[i]*primes[j]; break; }
        }
    }
}