首页 > 代码库 > leetcode-204-Count Primes
leetcode-204-Count Primes
Count Primes
Description:
Count the number of prime numbers less than a non-negative number, n.
题目 Count Primes
计算小于n的全部素数的总数。
用一般的方法超时,应该用筛选法求素数 ,參考 筛选法求素数
class Solution { public: int countPrimes(int n) { int* a = new int[n](); int ans = 0; int m = sqrt(n); for (int i = 2;i <= m;i++) { if (!a[i]) { for (int j = i * i;j < n;j = j + i) a[j] = 1;// 标记因子为i的合数 } } for (int i = 2;i < n;i++){ if (!a[i]) ans++; } return ans; } };
leetcode-204-Count Primes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。