204. Count Primes 求素數

Description:

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

題目大意：

輸出小于n的所有素數的個數。

思路：

采用厄拉多篩選法。

厄拉多塞篩法

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

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

其實，當你要畫圈的素數的平方大于 n 時，那么后面沒有劃去的數都是素數，就不用繼續判了。

代碼實現如下：

class Solution {
public:
    int countPrimes(int n)
    {
    	bool *Del = new bool[n];
    	//申請數組用來記錄某個數字是否被標記
    	if(n > 2)
    	    Del[2] = false;		
    	//先將數字2標記為素數
    	//某一數字標記為false表示該數為素數。
    	//某一數字標記為true表示該數為非素數。
    	for(int i = 3;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 &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 myset;//存放非素數
	myset.insert(1);
	for (int i = 2; i < n; i++)
	{
		if (myset.find(i) != myset.end())
			continue;
		if (!isPrimes(i))//如果不是一個素數
		{
			insertUnPrimesToSet(myset, i, n,0);
		}
		else//如果是一個素數
		{
			insertUnPrimesToSet(myset, i, n, 1);
		}
	}

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

2016-08-13 16:06:04

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