leetCode 204. Count Primes 哈希 求素数

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;i++)	
    	//将2的倍数都标记为非素数，将非2的倍数，标记为候选的素数。
    	{
    		if(i % 2 == 0)
    		{
    			Del[i] = true;
    		}
    		else
    			Del[i] = false;
    	}
    
    
    	for(int i = 3; i < n ;i++)
    	{
    		if(!Del[i])
    		{//如果当前数的平方大于目标数，那么当前数到
    		    //目标数中间的所有数都是素数。
    			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;//存放非素数
	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