[FIXED] Number of primes less than or equal to x

Issue

π(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)
  

Solution

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)

Answered By - President James K. Polk