189 8069 5689
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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。