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)

@AlexPetrosyan `nums.difference_update(set(range(p, x+1, p))` removes all multiples of p from `set(nums)`, where `nums` is a set of odd numbers. — , Sep 17 '21 at 11:43
Ok. Try to add a few debug `print`s to see what happens to multiples greater than 100 000. I suspect that at some point some operation fails silently. — Alex Petrosyan, Sep 17 '21 at 11:45
Perhaps you believe that `num.pop()` will remove the **smallest** element from the set, but I don't believe that is guaranteed. The docs for `pop()` say: *Remove and return an arbitrary element from the set.* — President James K. Polk, Sep 17 '21 at 13:39
@PresidentJamesK.Polk Thanks! `nums.difference_update(p, x+2*p, p)` is now giving correct answer correct answer. — , Sep 17 '21 at 15:35
That change doesn't make any sense to me. Why should that work? — President James K. Polk, Sep 17 '21 at 17:20
@PresidentJamesK.Polk even I don't know how but that's just working, And yes you are right `num.pop()` is really uncertain method to `pop()` the smallest element from the set — , Sep 18 '21 at 03:35

I'mahdi · Answer 1 · 2021-09-17T12:31:10.337

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

President James K. Polk · Accepted Answer · 2021-09-18T12:19:04.407

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)

Number of primes less than or equal to x

π(x) = Number of primes ≤ x

2 Answers2

Linked