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.
请登录之后再进行评论