204. Count Primes 求素?cái)?shù)

專注于為中小企業(yè)提供網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)鄂爾多斯免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了千余家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

Description:

Count the number of prime numbers less than a non-negative number, n.

題目大意：

輸出小于n的所有素?cái)?shù)的個(gè)數(shù)。

思路：

采用厄拉多篩選法。

厄拉多塞篩法

西元前250年，希臘數(shù)學(xué)家厄拉多塞(Eeatosthese)想到了一個(gè)非常美妙的質(zhì)數(shù)篩法，減少了逐一檢查每個(gè)數(shù)的的步驟，可以比較簡(jiǎn)單的從一大堆數(shù)字之中，篩選出質(zhì)數(shù)來(lái)，這方法被稱作厄拉多塞篩法(Sieve of Eeatosthese)。

具體操作：先將 2~n 的各個(gè)數(shù)放入表中，然后在2的上面畫(huà)一個(gè)圓圈，然后劃去2的其他倍數(shù)；第一個(gè)既未畫(huà)圈又沒(méi)有被劃去的數(shù)是3，將它畫(huà)圈，再劃去3的其他倍數(shù)；現(xiàn)在既未畫(huà)圈又沒(méi)有被劃去的第一個(gè)數(shù) 是5，將它畫(huà)圈，并劃去5的其他倍數(shù)……依次類推，一直到所有小于或等于 n 的各數(shù)都畫(huà)了圈或劃去為止。這時(shí)，表中畫(huà)了圈的以及未劃去的那些數(shù)正好就是小于 n 的素?cái)?shù)。

其實(shí)，當(dāng)你要畫(huà)圈的素?cái)?shù)的平方大于 n 時(shí)，那么后面沒(méi)有劃去的數(shù)都是素?cái)?shù)，就不用繼續(xù)判了。

代碼實(shí)現(xiàn)如下：

class Solution {
public:
    int countPrimes(int n)
    {
    	bool *Del = new bool[n];
    	//申請(qǐng)數(shù)組用來(lái)記錄某個(gè)數(shù)字是否被標(biāo)記
    	if(n > 2)
    	    Del[2] = false;		
    	//先將數(shù)字2標(biāo)記為素?cái)?shù)
    	//某一數(shù)字標(biāo)記為false表示該數(shù)為素?cái)?shù)。
    	//某一數(shù)字標(biāo)記為true表示該數(shù)為非素?cái)?shù)。
    	for(int i = 3;i<n;i++)	
    	//將2的倍數(shù)都標(biāo)記為非素?cái)?shù)，將非2的倍數(shù)，標(biāo)記為候選的素?cái)?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ù)都是素?cái)?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：

耗時(shí)太長(zhǎng)。

代碼如下：

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;//存放非素?cái)?shù)
	myset.insert(1);
	for (int i = 2; i < n; i++)
	{
		if (myset.find(i) != myset.end())
			continue;
		if (!isPrimes(i))//如果不是一個(gè)素?cái)?shù)
		{
			insertUnPrimesToSet(myset, i, n,0);
		}
		else//如果是一個(gè)素?cái)?shù)
		{
			insertUnPrimesToSet(myset, i, n, 1);
		}
	}

	return n -1 - myset.size() ;
}

2016-08-13 16:06:04

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：leetCode204.CountPrimes哈希求素?cái)?shù)-創(chuàng)新互聯(lián)
當(dāng)前URL：http://aaarwkj.com/article24/dgoije.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、小程序開(kāi)發(fā)、品牌網(wǎng)站建設(shè)、云服務(wù)器、虛擬主機(jī)、域名注冊(cè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)