首页 > 代码库 > leetcode 204
leetcode 204
题目描述:
Description:
Count the number of prime numbers less than a non-negative number, n.
解法一：
遍历从1-n的所有整数，查看是否为质数，是质数借助一个则将该整数存入一个容器中，判断一个数是否为质数，可以遍历在容器中且小于n的平方根的质数，如果n可以被符合条件的质数整除，则这个数不是质数。代码如下：
class Solution {public: vector<int> prime_vec; bool isPrime(int n) { if (n<2) return false; else if (n == 2) return true; else if (n % 2 == 0) return false; else { int n_sqr = sqrt(n); for (int i = 0; prime_vec[i] <= n_sqr; i ++) { if(n % prime_vec[i] == 0) return false; } return true; } } int countPrimes(int n) { int counter = 0; for (int i = 1; i < n; i ++) { if (isPrime(i)) { prime_vec.push_back(i); counter ++; } } for (auto i = prime_vec.begin(); i != prime_vec.end(); i ++) { cout << *i << endl; } return counter; }};
解法二：
上述代码的执行效率不高，看了其他人的解题思路之后，豁然开朗，维基百科上有一个动态演示的效果图，算法思想名叫“晒数法”，连接如下：
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
看了这个效果图我马上进行了自己的实现，代码如下：
class Solution {public: int countPrimes(int n) { int counter = 0; if (n < 2) return counter; int upper = sqrt(n); vector<bool> flag_vec(n, false); int i = 2; while (i < n) { cout << i << endl; counter ++; if(i <= upper) { for (long long j = i * i; j < n; j += i) flag_vec[j] = true; } ++ i; while (flag_vec[i] == true) ++ i; } return counter; }};
可以很清楚地知道，解法二比解法一要好很多，因为在从小到大遍历的过程中，所有的数仅遍历一遍，这解法一虽然比暴力的O（n*n）的方法好一些，但是时间复杂度还是大于O（n）的，而晒数法的时间复杂度仅为O（n）。
leetcode 204
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。