Fast Python Solution


  • 69
    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.

  • 2
    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.


  • 1

    @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.


  • 0
    S

    @david148877 len() counts how many of the items in primes[], thus replace them with 0/False.


  • 0
    O

    It should be O(n) solution, right? because it almost only visit each number once


Log in to reply
 

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