【LeetCode 204】关关的刷题日记39 Count Primes
关关的刷题日记39–Leetcode 204. Count Primes
题目
Count the number of prime numbers less than a non-negative number, n.
题目的意思是让求小于n的素数的个数。
方法1：本来最简单的想法是遍历3到的数，都不是n的约数的就是素数，反之就是合数，结果超时了。后来师父给指点了下：如果一个数是合数的话，那么肯定有质因子，所以实际上我们只需要遍历3到 之间的素数就可以了。
class Solution {public:
int countPrimes(int n) {
if(n<3)
return 0;
int re=0;
vector<int>primes;
primes.push_back(2);
for(int i=3; i<n; i=i+2)
{
int flag=1;
for(int x:primes)
{
if(x*x>n)
break;
if(i%x==0)
{
flag=0;
break;
}
}
if(flag)
primes.push_back(i);
}
return primes.size();
}};方法二：厄拉多塞筛法求素数。看了一下网上这一篇博客介绍得很好：http://blog.csdn.net/tsbyj/article/details/47254069，大家可以参考下。
class Solution {public:
int countPrimes(int n) {
if(n<3)
return 0;
int re=0;
vector<int>primes(n,1);
for(int i=2; i*i<n; ++i)
{
if(primes[i]==1)
{
for(int j=i; j*i<n; ++j)
{
primes[i*j]=0;
}
}
}
for(int x:primes)
{
re+=x;
}
return re-2;
}};人生易老，唯有陪伴最长情，加油！
以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2017-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
