Number Of Primes Less Than Or Equal To X

π(x) = Number of primes ≤ x Below code gives number of primes less than or equal to N It works perfect for N<=100000, Input - Output Table | Input | Output | |

Solution 1:

You code is only correct if nums.pop() returns a prime, and that in turn will only be correct if nums.pop() returns the smallest element of the set. As far as I know this is not guaranteed to be true. There is a third-party module called sortedcontainers that provides a SortedSet class that can be used to make your code work with very little change.

import time

import sortedcontainers
from operator import neg


defpi(x):
    nums = sortedcontainers.SortedSet(range(3, x + 1, 2), neg)
    nums.add(2)
    # print(nums)
    prm_lst = set([])
    while nums:
        p = nums.pop()
        prm_lst.add(p)
        nums.difference_update(set(range(p, x + 1, p)))
    # print(prm_lst)return prm_lst


if __name__ == "__main__":
    N = int(input())
    start = time.time()
    print(len(pi(N)))
    end = time.time()
    print(end - start)

Solution 2:

You can read from this thread the fastest way like below and with this function for n = 1000000 I find correctly 78498 prime numbers. (I change one line in this function)

From:

return ([2] + [i for i in range(3,n,2) if sieve[i]])

To:

returnlen([2] + [i for i in range(3,n,2) if sieve[i]])

Finally:

defprimes(n):
    sieve = [True] * n
    for i inrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    returnlen([2] + [i for i inrange(3,n,2) if sieve[i]])

inp =  [10, 100, 1000, 10000, 100000, 1000000]
for i in inp:
    print(f'{i}:{primes(i)}')

Output:

10:4100:251000:16810000:1229100000:95921000000:78498