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
Post a Comment for "Number Of Primes Less Than Or Equal To X"