Leetcode 204. Count Primes (python+cpp)

题目

解法1：brutal force（TLE）

这道题目非常简单，但是我在面uber的时候遇到过。首先就是直接暴力求解，根据定义就是质数只能被1和自己整除，当然要考虑到1这个特殊情况。
python代码如下：

class Solution:def countPrimes(self, n: int) -> int:def isprime(num):for i in range(2,num):if num%i==0:return Falsereturn Truecount = 0for i in range(2,n):if isprime(i):count += 1return count

解法2：埃氏筛法

从1到n遍历，假设当前遍历到m，则把所有小于n的、且是m 的倍 数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。埃氏筛法时间复杂度是nlogn，具体证明查一下吧，有点复杂的
python代码如下：

class Solution:def countPrimes(self, n: int) -> int:if n<=2:return 0prime = [True]*ncount = n-2for i in range(2,n):if prime[i]:for j in range(2*i,n,i):if prime[j]:prime[j] = Falsecount -= 1return count

C++版本如下：

class Solution {
    
public:int countPrimes(int n) {
    if (n<=2) return 0;vector<int> prime(n,true);int count = n-2; //需要除掉1和n本身for (int i=2;i<n;i++){
    if (prime[i]){
    for (int j=2*i;j<n;j+=i){
    if (prime[j]){
    prime[j] = false;count --;}}}}return count;}
};