• 注册
• 查看作者
• # Lincode：1324. Count Primes

### 1324. Count Primes

Count the number of prime numbers less than a non-negative number, n.

### Example

Example 1：

```Input: n = 2
Output: 0```

Example 2：

```Input: n = 4
Output: 2
Explanation：2, 3 are prime number```

```class Solution:
"""
@param n: a integer
@return: return a integer
"""
def countPrimes(self, n):
# write your code here
prime =  [1] * n
prime[0] = prime[1] = 0
for each in range(2,int(n**0.5)+1):
if prime[each]:
prime[each*each: n: each] = [0] * len(prime[each*each:n:each])

return sum(prime)```

First, we assume all numbers from 0 to N are prime, so as True.

Then, set number 0 and 1 to false, because they are not prime

from 2 to int(n**0.5) +1 is for calculation improvement, to reducing those number that after.

You can do 2 to n if you want, but there is no point to do that.

Example: n = 25, because they're the results of each*each all be all above 25 after we check number 5.

Why we check the prime [each*each] instead of their multiplier? For example, N =25.

Becuase for prime [each*2] we already marked as none prime when each = 2, same as 3, 4 each

prime[each*each: n: each] = [0] * len(prime[each*each:n:each])

will set all numbers of square of number, and increamental of itself to False.

Calculate the sum of prime, which is all true prime.

纽约州·纽约
• 0
• 0
• 0
• 904
• 请登录之后再进行评论

• 做任务
• 全部清空