title: Count the number of prime numbers less than a non-negative number, n in Python
body: <p>I am solving a coding question from <a href="https://leetcode.com/problems/count-primes/" rel="nofollow noreferrer">leetcode</a> in which we are supposed to Count the number of prime numbers less than a non-negative number, n. </p>
  
  <p>This is my solution:</p>
  
  <pre><code>class Solution(object):
  
      def isPrime(self, Number):
          return 2 in [Number, 2**Number % Number]
  
      def countPrimes(self, n):
          """
          :type n: int
          :rtype: int
          """
          count_prime = 0
          prime_range = filter(lambda x: x % 2 != 0 and x % 3 != 0 and x % 5 != 0, xrange(n))
  
          for i in prime_range:
              if self.isPrime(i):
                  count_prime += 1
  
          return count_prime
  
  print Solution().countPrimes(499979)
  </code></pre>
  
  <p>While this works for smaller numbers, it is taking a lot of time for larger numbers and I am not sure where which part is consuming more time in my program? Here I am testing for numbers greater than 100 only.</p>
  
  <blockquote>
    <p>Could anyone help me to find which part is taking more time</p>
  </blockquote>