Fast Python Solution


  • 59
    T
    class Solution:
    # @param {integer} n
    # @return {integer}
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

  • 2
    A
    class Solution(object):
        def countPrimes(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 2:
                return 0
            
            prime = [True] * n
            prime[:2] = [False, False]
            for base in xrange(2, int((n - 1) ** 0.5) + 1):
                if prime[base]:
                    prime[base ** 2::base] = [False] * len(prime[base ** 2::base])
            return sum(prime)
    

    Your code is very brilliant! I adopt it and add some modifications.

    1. Because numbers LESS THAN n are considered, we can just (n - 1) ** 0.5.
    2. When slicing, default index can be used.

  • 1
    W

    is 2 a prime? so if n ==2 would return 1?


  • 0
    B

    here is my test about some code ,this might good for improve speed

    ➜  ~  python -m timeit -s 'int(3 ** 0.5) + 1'
    100000000 loops, best of 3: 0.0119 usec per loop
    ➜  ~  python -m timeit -s 'int(3 ** 0.5 + 1)'
    100000000 loops, best of 3: 0.0117 usec per loop
    ➜  ~  python -m timeit -s 'l = [False] * 1000' 'l[0] = l[1] = True'
    10000000 loops, best of 3: 0.102 usec per loop
    ➜  ~  python -m timeit -s 'l = [False] * 1000' 'l[:2] = [True, True]'
    10000000 loops, best of 3: 0.172 usec per loop

  • 0
    S

    Could someone please explain me what this line does?
    primes[i * i: n: i] = [False] * len(primes[i * i: n: i])


  • 0
    X

    Could not be better!


  • 0

    @warm2000 the description said that less than n


  • 0

    could I omit the n < 3 judgement? I tried and was accepted


  • 0
    W

    if you try:

    primes = [1,2,3,4,5,6,7,8,9,10]

    primes[3:10:2] = [0]*len(primes[3:10:2])

    print primes

    you will see what's going on.


  • 0
    W

    Genius man! perfectly solved the "time limit exceeds" issue.


  • 0

    Nice use of the eratosthenes theorem! (ง •̀_•́)ง


  • 0
    T
    This post is deleted!

  • 1
    B

    @sjayster If i is a prime, then i * i, i * (i +1), i * (i + 2) ... cannot be primes, as they are all divided by i.


  • 0
    C

    Great solution.
    I think we can calculate len(primes[i*i:n:i]) ourself for optimization

    ...
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            primes[i * i: n: i] = [False] * ((n-i*i-1)/i + 1)
    ...
    

    The code will beat about 98% after the modification.


  • 0

    @warm2000 2 is a prime but if n ==2 it should return 0 because we need to count the number of prime numbers less than a non-negative number. only 1 is less then 2. And 1 is not a prime.


  • 0

    @sjayster
    Try to go through the code and it will explain all:

    for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
    

    let`s assume n == 100, we need to count all the primes which are less than 100:
    when i == 2:

    primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
    

    It will mark out the numbers as none-prime:
    4: 100 : 2 ---> 4,6,8,10,12,14 ... 100
    which makes prime[4] =False, prime[6]=False, prime[8]=False....

    similarly:
    when i ==3:
    9: 100 : 3 -- > 9,12,15,18,21,24... 96, 99
    when i == 4:
    16: 100 :4 --> 16,20,24,28.... 96,100
    ...
    ...
    So if n is not a prime, prime[n] = False, otherwise, prime[n] = True, which is 1 in math.
    So sum the whole list, you will get the count of primes.


  • 0
    D

    in

    for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
    

    why it must multiply with lenth???


  • 0
    N

    @tusizi said in Fast Python Solution:

    primes[i * i: n: i] = [False] * len(primes[i * i: n: i])

    for j in range(i * i, n, i):
      primes[j] = False
    

    Much cleaner this way.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.