Leecode刷题之旅-C语言/python-204计数质数

/*

 * @lc app=leetcode.cn id=204 lang=c

 *

 * [204] 计数质数

 *

 * https://leetcode-cn.com/problems/count-primes/description/

 *

 * algorithms

 * Easy (26.72%)

 * Total Accepted:    13.8K

 * Total Submissions: 51.6K

 * Testcase Example:  '10'

 *

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

 *

 * 示例:

 *

 * 输入: 10

 * 输出: 4

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

 *

 *

 */

int countPrimes(int n) {

    int i,j,count=;

    if(n<=){

        return ;

    }

    for(i=;i<=n;i+=){

        for(j=;j<=sqrt(i);j++){

            if(i%j==){

                break;

            }

        }

        if(j>sqrt(i))

            count++;

    }

    return count;

}

统计质数还是很简单的。

-------------------------------

python：

#

# @lc app=leetcode.cn id=204 lang=python3

#

# [204] 计数质数

#

# https://leetcode-cn.com/problems/count-primes/description/

#

# algorithms

# Easy (26.72%)

# Total Accepted:    13.8K

# Total Submissions: 51.6K

# Testcase Example:  '10'

#

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

#

# 示例:

#

# 输入: 10

# 输出: 4

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

#

#

#

class Solution:

    def countPrimes(self, n: int) -> int:

        if n <= 2:

            return 0

        res = [True] * n

        res[0] = res[1] = False

        for i in range(2, n):

            if res[i] == True:

                for j in range(2, (n-1)//i+1):

                    res[i*j] = False

        return sum(res)