Python beat 99.97%. With idea discription


  • 0
    X

    Idea: if er are looking at 3, the 33=9, 34=12, 35=15, 36=18, ... will not be prime. So we set a trueTable, and "predict" all numbers that will not be prime, and set them to False.

    Also we just need to check from 2 to n^(1/2.0) because all numbers bigger than n^(1/2.0) has been set to either False or True.

    Finally, we count how many True we have in or trueTable

    class Solution(object):
        
        def countPrimes(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 2: return 0
            if n == 2: return 0
            res = 1
            
            trueTable = [True]*n
            trueTable[0:2] = [False]*2
            for i in range(2, int(n**0.5) + 1):
                if trueTable[i] == True:
                    trueTable[i*2:n:i] = [False]*((n - 1 - i*2)/i + 1)
            return sum(trueTable)
    

  • 0
    S

    What is the time complexity of this solution?


  • 0
    R

    Can you explain this part of your code

    trueTable[i*2:n:i] = [False]*((n - 1 - i*2)/i + 1)


Log in to reply
 

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