這個文章主要介紹了3算法
1線性時間篩素數(shù)
2線性時間求前n個數(shù)的歐拉函數(shù)值
3線性時間求前n個數(shù)的約數(shù)個數(shù)
一、 首先介紹下積性函數(shù)。
下面是wiki的條目：
在非數(shù)論的領(lǐng)域，積性函數(shù)指有對于任何a,b都有性質(zhì)f(ab)=f(a)f(b)的函數(shù)。
在數(shù)論中的積性函數(shù)。對于正整數(shù)n的一個算術(shù)函數(shù)f(n)，當(dāng)中f(1)=1且當(dāng)a,b互質(zhì)，f(ab)=f(a)f(b)，在數(shù)論上就稱它為積性函數(shù)。
若某算術(shù)函數(shù)f(n)符合f(1)=1，且就算a,b不互質(zhì)，f(ab)=f(a)f(b)，稱它為完全積性的。
例子
φ(n) －歐拉φ函數(shù)，計算與n互質(zhì)的正整數(shù)之?dāng)?shù)目
μ(n) －默比烏斯函數(shù)，關(guān)于非平方數(shù)的質(zhì)因子數(shù)目
gcd(n,k) －最大公因子，當(dāng)k固定的情況
d(n) －n的正因子數(shù)目
σ(n) －n的所有正因子之和
σk(n): 因子函數(shù)，n的所有正因子的k次冪之和，當(dāng)中k可為任何復(fù)數(shù)。在特例中有：
σ0(n) = d(n) 及
σ1(n) = σ(n)
1(n) －不變的函數(shù)，定義為 1(n)=1 （完全積性）
Id(n) －單位函數(shù)，定義為 Id(n)=n （完全積性）
Idk(n) －冪函數(shù)，對于任何復(fù)數(shù)、實數(shù)k，定義為Idk(n) = nk （完全積性）
Id0(n) = 1(n) 及
Id1(n) = Id(n)
ε(n) －定義為：若n = 1，ε(n)=1；若n > 1，ε(n)=0。有時稱為“對于狄利克雷回旋的乘法單位”（完全積性）
(n/p) －勒讓德符號，p是固定質(zhì)數(shù)（完全積性）
λ(n) －劉維爾函數(shù)，關(guān)于能整除n的質(zhì)因子的數(shù)目
γ(n)，定義為γ(n)=(-1)ω(n)，在此加性函數(shù)ω(n)是不同能整除n的質(zhì)數(shù)的數(shù)目
所有狄利克雷特性均是完全積性的
二、再介紹下線性篩素數(shù)方法
bool notp[mr];//素數(shù)判定
__int64 pr[670000],pn,ans;//pr存放素數(shù),pn當(dāng)前素數(shù)個數(shù)。
void getprime()
{
pn=0;
memset(notp,0,sizeof(notp));
for(int i=2;i<mr;i++)
{
if(!notp[i])pr[pn++]=i;
for(int j=0;j<pn && pr[j]*i<mr;j++)
{
notp[pr[j]*i]=1;
if(i%pr[j]==0)break;
}
}
}
利用了每個合數(shù)必有一個最小素因子。
每個合數(shù)僅被它的最小素因子篩去正好一次。所以為線性時間。
代碼中體現(xiàn)在：
if(i%pr[j]==0)break;
pr數(shù)組中的素數(shù)是遞增的,當(dāng)i能整除pr[j]，那么i*pr[j+1]這個合數(shù)肯定被pr[j]乘以某個數(shù)篩掉。
因為i中含有pr[j],pr[j]比pr[j+1]小。接下去的素數(shù)同理。所以不用篩下去了。
在滿足i%pr[j]==0這個條件之前以及第一次滿足改條件時,pr[j]必定是pr[j]*i的最小因子。
三、結(jié)合線性篩素數(shù)算法的優(yōu)化算法
基于這個線性篩素數(shù)算法,我們可以很容易地得到某個數(shù)的最小素因子。
因為當(dāng)i%pr[j]!=0的時候,最小素因子pr[j]與i互質(zhì),滿足積性函數(shù)的條件,可以直接得到f(i*pr[j])=f(i)*f(pr[j]).
不過當(dāng)i%pr[j]==0時我們必須根據(jù)該積性函數(shù)本身的特性進(jìn)行計算.或者在篩的同時保存并遞推些附加信息.總之要O(1)求得f(i*pr[j])及完成遞推附加信息.
下面的兩個例子是歐拉函數(shù)phi和約數(shù)個數(shù).這兩個是最常用和最有優(yōu)化價值的。
利用上面的性質(zhì)都可以很容易地把前n個用O(n)時間推出來.
當(dāng)然，利用這個性質(zhì)還可以對其他積性函數(shù)進(jìn)行優(yōu)化，這里僅介紹兩個常用和有優(yōu)化價值的。
1)歐拉函數(shù)(phi)
傳統(tǒng)的算法:
對于某素數(shù)p且n|p(n能整除p)
if( (n/p) % i == 0 ) phi(n)=phi(n/p)*i;
else phi(n)=phi(n/p)*(i-1);
這個傳統(tǒng)算法的性質(zhì)正好用在篩素數(shù)算法中.
p為n的最小素因子,當(dāng)n/p包含該因子p,則phi(n)=phi(n/p)*i;否則phi(n)=phi(n/p)*(i-1);
p即pr[j], n/p即i, n即i*pr[j]了.
2)約數(shù)個數(shù)(divnum)
約數(shù)不能像phi那么自然,但還是有不錯的方法.
約數(shù)個數(shù)有個性質(zhì)
divnum(n)=(e1+1)*(e2+1)...(ei表示n的第i個質(zhì)因數(shù)的個數(shù).)
傳統(tǒng)方法就是對每個數(shù)分解質(zhì)因數(shù),獲得各因數(shù)個數(shù)再用上式.
開一個空間e[i]表示最小素因子的次數(shù)
這次說直接點(diǎn):
篩到i 第j個素數(shù)
對于divnum
如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數(shù)加1
否則 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //滿足積性函數(shù)條件
對于e
如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次數(shù)加1
否則 e[i*pr[j]]=1; //pr[j]為1次
轉(zhuǎn)自：
http://hi.baidu.com/cjhh314/blog/item/bfe13bce20fb7c3db600c85c.html