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