leetCode 204 計數質數（埃氏篩法）

題目連結：點選檢視

題目描述：

給定一個數字 n ，求小于 n 的質數的個數。   輸入輸出：  

輸入：n = 10
輸出：4
      

輸入：n = 1
輸出：0      

題目分析：

本題用埃氏篩法（素數篩）可以十分簡便的解出這道題，其原理為從 1 到 n 周遊，假設目前周遊到 m，則把所有小于 n 的、且是 m 的倍數的整數标為和數；周遊完成後，沒有被标為和數的數字即為質數。

代碼：

int countPrimes(int n)
{
	if(n<=2)
	return 0;
	vector<bool>prime(n,true);
	int count=n-2;//去掉不是質數的1
	for(int i=2;i<=n;++i)
	{
	   if(prime[i])
	   for(int j=2*i;j<n;j+=i)
	   {
	   	if(prime[j])
	   	{
	   	    prime[j]=false;
			--count;	
		}
	   }
	}
	return count; 
}
           

優化： 利用素數的一些特性可以對代碼進行優化

int countPrimes(int n)
{
	if(n<=2)
	return 0;
	vector<bool>prime(n,true);
    int i=3,sqrtn=sqrt(n),count=n/2;//偶數一定不是質數
	while(i<=sqrtn)//最小質因子一定小于等于開方數 
	{
	   for(int j=i*i;j<n;j+=2*i)//避免偶數和重複周遊
	   {
	   	if(prime[j])
		{
		   --count;
		   prime[j]=false;   	
		} 
	   }
	   do
	   {
	   	 i+=2;
	   	 
		}while(i<=sqrtn&&!prime[i]);//避免偶數和重複周遊	
	}
	return count;	
}