求出1~N范圍中所有的素?cái)?shù)，在leetcode中做過這個(gè)題目，我想從對(duì)每個(gè)1~N進(jìn)行一次遍歷，每個(gè)數(shù)判斷一次是否是素?cái)?shù)。
判斷一個(gè)數(shù)是否是素?cái)?shù)的復(fù)雜度本身也是挺高的，再進(jìn)行一次迭代，在leetcode中的結(jié)果是超時(shí)：
class Solution {PRivate: bool isPrime(int n) { int sqrt_=sqrt(n); int i; for (i=2;i<=sqrt_;++i) { if(n%i==0) break; } if(i>sqrt_) return true; else return false; }public: int countPrimes(int n) { int count=0; for(int i=2;i<n;++i) { if(isPrime(i)) ++count; } return count; }};既然篩選，先假定1~N全是素?cái)?shù)，然后從第一個(gè)素?cái)?shù)2的平方4開始，去掉因子包括2的數(shù)，例如4、6、8…. 然后從后一個(gè)素?cái)?shù)3的平方9開始剔除，因子包括3的數(shù)，例如9、12等。。。
最后剩下的數(shù)就是所有的素?cái)?shù)。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
