參考文獻：《資訊奧賽一本通》，《演算法競賽指南》
簡單概述？
首先我們都知道，質數是一個正整數，無法被除了1和它自身之外的任何自然數整除，若不滿足，則這個正整數為合數，
算識訓本定理：
每一個大于1的正整數都可以唯一分解成有限個質數的乘積，如：
5=1*5 6=2*3 18=2*2*3 .......
質數分布定理：
（說實話這個我還沒搞懂，等我搞懂再來補充）
質數判定：
試除法
若一個正整數A為合數，則必定存在一個能整除A的數T，其中2 <= T <= sqrt(A);
證明：我們可以用·反證法· ，即假設以上的結論不成立，則必定存在T滿足sqrt(A)+1 <= T <= A-1；
因為 A / T == K，且T整除A，則K也一定整除A，但是K一定在2 <= K <=sqrt(A)中，所以假設不成立，原命題成立，(sqrt 為開根號）
根據這個定理我們可以發現，只要掃描從2到sqrt(A)間所有整數是否整除A，可以就為合數，否則為質數，
代碼如下(時間復雜度為 O(sqrt(N)) )
bool is_prime(long n){
for(long i=2;i<=sqrt(n);i++)
if (n%i==0) return 0;
return 1;
}
當然我們可以用“Miller-Robbin”，多次判定出錯率接近0，在這里就不介紹了，
質數的篩選
No.1 Eratosthenes 篩法 （簡稱埃氏篩）
它的思想是，只要是質數的倍數就一定不是質數， 因為質數的倍數它一定可以表示成某個質數*倍數形式，不滿足質數的定義，
操作：從小到大列舉每一個質數，但只要是質數的倍數就全部標記成非質數,整數1特殊處理，
例如程序如下：
2 3 4 5 6 7 8 9 10 11 12 ...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
但是事實上6 會被2 和 3同時標記為合數，則說明小于x2（x的平方）的x的倍數在之前掃描更小的數時就已經標記過了，所以我們可以優化這個篩法，
對于每一個x，把 >= x2的x的倍數標記為合數就可以了，即掃描x時從x2開始標記就行，
演算法復雜度為O(n logn logn)，接近線性
bool v[MAXN]; //合數標記
void primes(long n){
memset(v,0,sizeof v);
for(long i=2;i<=n;i++){
if(v[i]) continue;
cout<<i<<endl; //i是質數
for(long j=i;j<=n/i;j++) v[i*j]=1; //累計倍數
}
}
No.2 線性篩法
即使是優化后的Eratosthenes演算法，它還是會有重復標記發生，例如12 還是會被2，3重復標記，它時間復雜度較高的根源是它無法唯一確定某個合數的產生方式，
而線性篩法是通過“從大到小累積質因子”的方法去標記每個合數，因為每個合數只會被它的最小質因子篩一次，時間復雜度為O(N)，原理是算識訓本定理
代碼如下
long v[MAXN],prime[MAXN];
void primes(long n){
memset(v,0,sizeof v); //v表示最小質因子
long m=0;//質數數量
for(long i=2;i<=n;i++){
if(v[i]==0){//i為質數
v[i]=i;
prime[++m]=i;
}
//給i乘上一個質因子
for(long j=1;j<=m;j++){
if(prime[j]>v[i] || i*prime[j]>n) break;//若這個質數大于i的最小質因子，或者超出n的范圍，就終止回圈
v[prime[j]*i]=prime[j]; //這樣就可以得到prime[j]必定為prime[j]*i的最小質因子 （prime[j]<=v[i])
}
}
for(long i=1;i<=m;i++) printf("%ld\n",prime[i]);
}
質因數分解
它要根據算數基本定理來分解
任何一個大于1的正整數都能唯一分解為有限個質數的乘積（ai為正整數，pi為質數，p1<p2<......<pn）方法：試除法
我們可以掃描從2~sqrt(N)的每個數k，并判斷k是否整除N，若成立，則繼續除下去直到N無法被k整除 ，即除去N中所有的因子并記錄除去的k值個數 這樣的話，N的合數因子一定在掃描到它之前就被除去了，因為根據算數基本定理，這個合數因子也可以被分解質因數，而它的質因數也是原合數的質因數， 所以在之前就必定被抹殺了...... 當然如果N無法被2~sqrt(N)整除，則說明N是質數，應注意不要漏了， 時間復雜度為O( sqrt(N) )，void divide(long n){
long m=0; //質數數量
for(long i=2;i<=sqrt(n);i++){
if(n%i==0){ //若成立，則i必定為質數
prime[++m]=i;
a[m]=0;
while(n%i==0) n/=i,a[m]++;
}
if(n>1) //說明n本身為質數，無需分解
p[++m]=n;a[m]=1;
}
for(long i=1;i<=m;i++)
printf("%ld^%ld\n",p[i],a[i]);
}
就這樣吧...... 比較菜，若有問題望及時提出謝謝，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21343.html
標籤：其他