前言
今天做ACM的時候,遇到了素數的檢測,檢測一個范圍內的素數的時候,如果用最簡單的那種方法,超時嚴重,因此學習了一個新的素數檢測算法——素數篩選法,這里也是跟大家分享一下
素數
素數的定義
一個大于1的整數,如果不能被除1和它本身之外的其它正整數整除,則是素數(又稱質數)
合數的定義
一個大于1的整數,如果不是素數則是合數。其中能整除這個數的正整數叫做約數,不等于1也不等于合數本身的約數叫做非平凡約數。
注意:
1既不是素數也不是合數
檢測素數
所謂素數檢測,就是給定任意一個大于1的整數,判斷這個整數是否為素數。
因子檢測法
方法:就是從2到n-1一個個的拿來嘗試,看能否整除n,如果存在能夠整數n的(找到一個因子),則n不是素數,否則認為n是素數。實際,是不需要試探到n-1的,只要的n的二次方根即可,原因是:
設n = a * b,且a、b均為n非平凡約數,顯然a > n的二次方根和b > n的二次方根不可能同時成立,因為同時成立時 a * b就會大于n,所以如果n存在非平凡約數,至少有一個小于等于n的二次方根,因此只要遍歷到n的二次方根即可。
因子檢測的實現代碼如下(c):
int isPrime(int n) { int i, flag; flag = (n <= 1)? 0 : 1; for(i = 2; i <= sqrt(n); i ++) { if(n % i == 0) { flag = 0; break; } } return flag; }
測試結果:
時間復雜度:
很明顯,因子檢測算法的時間復雜度是0(n的二次方根),一般來說,這個時間復雜度已經很牛叉了,但是如果我要求n以內所有的素數集合,那時間復雜度瞬間就到了n * n的二次方根,這個對于n很大時是不可忍受的
素數篩選法
利用素數因子檢測法去超找n以內的所有素數,時間復雜度太高,不可忍受,因此這里介紹另外一種算法,素數篩選法,可以大大的節省時間,帶來的直接功效是九度acm關于素數檢測的題我瞬間ac,用素數因子檢測基本都是wa。
原理:
當i是素數的時候,則i的所有倍數必然是合數。如果i已經判斷不是素數了,那么找到i后面的質數來把這個質樹的倍數篩掉。
求20以內素數的篩選過程:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第一步,因為所有的偶數和0,1必然不是質數,則將這些數的對應的value標記為flase,其余為true。
第二步:
i = 3,由于prime[3] = 1,則prime[6],prime[9],prime[12],prime[15],prime[18]均標記為0;
i = 4,由于prime[4] = 0,則continue,不做處理;
i = 5 > sqrt(20),算法結束
時間復雜度:
這個時間復雜度由于我的數學知識有限,也沒法把計算過程解釋出來,總之確實是很快,至于為什么i= 5就結束了,原因跟素數因子法里面的原理是一樣的,因為n的因子必然有一個是小于等于n的二次方根的。
素數篩選法實現代碼:
void getPrimeArray(int *prime) { int i, j; //初始化素數標識數組 for(i = 0; i < max; i ++) { if((i == 2 || i % 2 != 0) && i != 1) { prime[i] = 1; } else { prime[i] = 0; } } //進行素數的篩選 for(i = 2; i * i < max; i ++) { if(prime[i]) { for(j = 2 * i; j < max; j += i) { prime[j] = 0; } } } }
參考資料
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
