您好,登錄后才能下訂單哦!
204. Count Primes 求素數(shù)
Description:
Count the number of prime numbers less than a non-negative number, n.
題目大意:
輸出小于n的所有素數(shù)的個數(shù)。
思路:
采用厄拉多篩選法。
西元前250年,希臘數(shù)學(xué)家厄拉多塞(Eeatosthese)想到了一個非常美妙的質(zhì)數(shù)篩法,減少了逐一檢查每個數(shù)的的步驟,可以比較簡單的從一大堆數(shù)字之中,篩選出質(zhì)數(shù)來,這方法被稱作厄拉多塞篩法(Sieve of Eeatosthese)。
具體操作:先將 2~n 的各個數(shù)放入表中,然后在2的上面畫一個圓圈,然后劃去2的其他倍數(shù);第一個既未畫圈又沒有被劃去的數(shù)是3,將它畫圈,再劃去3的其他倍數(shù);現(xiàn)在既未畫圈又沒有被劃去的第一個數(shù) 是5,將它畫圈,并劃去5的其他倍數(shù)……依次類推,一直到所有小于或等于 n 的各數(shù)都畫了圈或劃去為止。這時,表中畫了圈的以及未劃去的那些數(shù)正好就是小于 n 的素數(shù)。
其實,當(dāng)你要畫圈的素數(shù)的平方大于 n 時,那么后面沒有劃去的數(shù)都是素數(shù),就不用繼續(xù)判了。
代碼實現(xiàn)如下:
class Solution { public: int countPrimes(int n) { bool *Del = new bool[n]; //申請數(shù)組用來記錄某個數(shù)字是否被標(biāo)記 if(n > 2) Del[2] = false; //先將數(shù)字2標(biāo)記為素數(shù) //某一數(shù)字標(biāo)記為false表示該數(shù)為素數(shù)。 //某一數(shù)字標(biāo)記為true表示該數(shù)為非素數(shù)。 for(int i = 3;i<n;i++) //將2的倍數(shù)都標(biāo)記為非素數(shù),將非2的倍數(shù),標(biāo)記為候選的素數(shù)。 { if(i % 2 == 0) { Del[i] = true; } else Del[i] = false; } for(int i = 3; i < n ;i++) { if(!Del[i]) {//如果當(dāng)前數(shù)的平方大于目標(biāo)數(shù),那么當(dāng)前數(shù)到 //目標(biāo)數(shù)中間的所有數(shù)都是素數(shù)。 if(i*i >=n) break; for(int j = 2;i*j < n; j++) Del[i*j] = true; } } int count = 0; for(int i = 2;i < n;i++) { if(!Del[i]) count++; } delete [] Del; return count; } };
思路2:
耗時太長。
代碼如下:
bool isPrimes(int n) { if (n == 2) return true; int middle = (int)sqrt(double(n)); for (int i = 2; i <= middle; i++) { if (n % i == 0) return false; } return true; } void insertUnPrimesToSet(set<int> &myset, int n,int max,int flag) { int times = (max-1) / n; if (flag == 0) { for (int i = 1; i <= times; i++) { myset.insert(n*i); } } else if (flag == 1) { for (int i = 2; i <= times; i++) { myset.insert(n*i); } } } int countPrimes(int n) { if (n <= 2) return 0; set<int> myset;//存放非素數(shù) myset.insert(1); for (int i = 2; i < n; i++) { if (myset.find(i) != myset.end()) continue; if (!isPrimes(i))//如果不是一個素數(shù) { insertUnPrimesToSet(myset, i, n,0); } else//如果是一個素數(shù) { insertUnPrimesToSet(myset, i, n, 1); } } return n -1 - myset.size() ; }
2016-08-13 16:06:04
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。