Number of primes less than or equal to x

Question

π(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      | 
  |-------------|---------------|
  | 10          |     4✔       |
  | 100         |     25✔      |
  | 1000        |     168✔     |
  | 10000       |     1229✔    |
  | 100000      |     9592✔    |
  | 1000000     |     78521✘   | 
  

  However, π(1000000) = 78498

  import time
  def pi(x):
      nums = set(range(3,x+1,2))
      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)
  

Answer 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


def pi(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)

Answer 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:

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

Finally:

def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return len([2] + [i for i in range(3,n,2) if sieve[i]])

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

Output:

10:4
100:25
1000:168
10000:1229
100000:9592
1000000:78498