每日一道算法题 204. 计数质数

题目

204. 计数质数 - 力扣（LeetCode）

Python

class Solution:
    def countPrimes(self, n: int) -> int:
        """
        质数又称为素数，是一个大于1的自然数，除了1和它自身外，
        不能被其他自然数整除的数叫做质数；否则称为合数。
        """
        # 埃氏筛
        # 质数的倍速(2，3，4……)是合数
        if n<2:
            return 0  #0，1不是质数
        # 假设全是质数
        is_primes=[1]*n
        is_primes[0]=is_primes[1]=0
        # n的质数以int(n**0.5)+1为对称轴分布在两边
        # [2,int(n**0.5)+1]，[int(n**0.5)+1,n]
        for i in range(2,int(n**0.5)+1):
            # 2*2,2*3...
            # 3*2,3*3... 不应该3*2，因为2*3已经标记过
            if is_primes[i]:
                for j in range(i*i,n,i):
                    is_primes[j]=0
        return sum(is_primes)

C++

class Solution {
public:
    int countPrimes(int n) 
    {
        vector<int> is_primes(n,1);//初始化n个值为1的元素
        int ans=0;
        if(n<=2) return 0;
        // is_primes[0]=0;
        // is_primes[1]=0;
        for(int i=2;i<sqrt(double(n))+1;i++)
        {
            if(is_primes[i])
            {
                //ans++;
                if((long long)i*i<n)
                {
                    for(int j=i*i;j<n;j+=i) is_primes[j]=0;
                }
            }

        }
    for(const auto& x:is_primes) ans+=x;

    return ans-2;
    
    }
   
};

C语言

int countPrimes(int n) 
{
    if (n < 2)  return 0;
    int isPrime[n];
    memset(isPrime, 1, sizeof(isPrime));
    int ans = 0;
    for (int i = 2; i < n; ++i)
    {
        if (isPrime[i]) {
            ans += 1;
            if ((long long)i * i < n) 
            for (int j = i * i; j < n; j += i) isPrime[j] = 0;
        }
    }
    return ans;
}