• 注册
    • 今日签到
    • 连续签到

    暂没有数据

    暂没有数据

    • 查看作者
    • 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
    • 153