LeetCode刷题（114）～计数质数【埃拉托色尼筛选法】

题目描述

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

  

 

  
1
  
2
  
3
 

解答 By 海轰

提交代码

bool is(int num) { for(int i=2;i<=sqrt(num);++i) { if(num%i==0) return false; } return true; } int countPrimes(int n) { int count=0; for(int i=2;i<n;++i) { if(is(i)==true) ++count; } return count; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

运行结果

解答

Demo（埃拉托色尼筛选法）

int countPrimes(int n) { int a[n+1]; for(int i=0;i<n;++i) a[i]=1; for(int i=2;i<=sqrt(n);++i) { if(a[i]==1) { for(int j=i*i;j<n;j+=i) a[j]=0; } } int count=0; for(int i=2;i<n;++i) if(a[i]==1) ++count; return count; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108336862