素數的判定與篩法

判定：很簡單嘛！暴力大法參上！

#include

#include

unsigned long int n,i,j,a,b;

using namespace std;

int main()

{

cin>>n;

j=(int)sqrt(n);

for(i=2;i<=j;i++)

if(n%i==0) break;

if(i>j&&n!=0&&n!=1) cout<

else cout<

}

(不相信從來不刷水的我竟然做了這樣的題……)

這就是傳說中的O(根號N)大暴力……

那么還有個算法叫Miller-rabin……

那么我們來介紹一下這是個什么東西：

首先讓我們了解這幾個概念：

費馬小定理：對于素數p和任意整數a，有ap?≡ a(mod p)(同余)。反過來，滿足ap?≡ a(mod p)，p也幾乎一定是素數。

偽素數：如果n是一個正整數，如果存在和n互素的正整數a滿足 an-1?≡ 1(mod n)，我們說n是基于a的偽素數。如果一個數是偽素數，那么它幾乎肯定是素數。

Miller-Rabin測試：不斷選取不超過n-1的基b(s次)，計算是否每次都有bn-1?≡ 1(mod n)，若每次都成立則n是素數，否則為合數。

設待測數為n，取一個比n小的正整數a,設n-1=d*2^r。若n是素數，則要么a^d mod n = 1,要么存在一個i,滿足0≤i＜r且a^(d*2^i )mod n = -1

經過獨立的t輪Miller-Rabin算法將一個合數誤判為素數的可能性不大于 (1/4)t，(正確實現的算法不會誤判素數為合 數)，這個誤判概率在基于Fermat定理的算法中是最好的。一輪Miller-Rabin算法的最壞情況時間復雜度為 (1+O(1))log2(n)( 以模n乘法為基本操作)。如果以單精度乘法操作作為時間復雜度的衡量，則一輪優化的Miller-Rabin算法的最 壞情況時間復雜度為O(log32 (n) 。從時間復雜度來看Miller- Rabin算法的性能是很好的。在實際應用中，Miller-Rabin 算 法的實際執行速度也很快。

大家可以多次調用該函數，使得錯誤率降低。

#include

#include

#include

bool witness(__int64 a,__int64 n)

{

__int64 t,d,x;

d=1;

int i=ceil(log(n-1.0)/log(2.0)) - 1;

for(;i>=0;i--)

{

x=d; d=(d*d)%n;

if(d==1 && x!=1 && x!=n-1) return true;

if( ((n-1) & (1< 0)

d=(d*a)%n;

}

return d==1? false : true;

}

bool miller_rabin(__int64 n)

{

if(n==2) return true;

if(n==1 || ((n&1)==0)) return false;

for(int i=0;i<50;i++){

__int64 a=rand()*(n-2)/RAND_MAX +1;

if(witness(a, n)) return false;

}

return true;

}

int main()

{

int n,cnt;

__int64 a;

while(scanf("%d",&n)!=EOF)

{

cnt=0;

while(n--)

{

scanf("%I64d",&a);

if(miller_rabin(a))

cnt++;

}

printf("%d\n",cnt);

}

return 0;

}

篩法：篩法有3種時間復雜度，詳細說應該有四種，最后一種貌似是打表……

1.O(N*根號N)

2.O(NlogN)

3.O(N)

第一種方法：很明顯的暴力啊……循環+判斷

第二種方法：這是比較常用的一種篩法：埃氏篩(俗稱垃圾篩)，根本思想很簡單：我們從1往N搜，假如我們遇到了一個沒有被標記為不是素數的數，那么我們把它的倍數(>1)都標記為非素數……

for(int i=2;i<=1000000;i++)

if(!FP[i])

{

PL[++e]=i;

for(long long j=(long long)i*i;j<=1000000;j+=i) FP[j]=1;

}

第三種方法：線性篩，這個還是根據代碼來解釋吧……

第一行：應該沒必要解釋吧

第二行：從1到N枚舉

第三行：同埃氏篩

第四行：枚舉素數

第五行：如果乘上i大于n了，那么后面也肯定大于n，so break……

第六行：把prime[j]的i倍標記為不是素數

第七行：這個是代碼的核心句，如果沒有這句，那么它的時間復雜度與埃氏篩一樣，但是我們來看一看12，它是在什么時候被枚舉到的？第6次循環，也就是說，我們這次如果不加這條語句，那么有寫情況是算重復了，那么這條魚句就可以保證它不會重復。

1. 任何一個合數都可以表示成一個質數和一個數的乘積

2. 假設A是一個合數，且A = x * y，這里x也是一個合數，那么有:一個合數(x)與一個質數(y)的乘積可以表示成一個更大的合數(Z)與一個更小的質數(a)的乘積

例如: 如果i = 8; 那么由于i%2 == 0; 因此對于i=8就只需要檢查primes[1]=2即可，因為對于大于primes[1]的質數，像3，有:8*3 = 2*4*3 = 12*2

也就是說24(8*3=24)并不需要在8時檢查，在12時才檢查

總結

以上是生活随笔為你收集整理的java 素数 五行_【数论】素数的判定与筛法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。