The prime-counting function is the function counting the number of prime numbers less than or equal to some positive integet $n$. We usually call the function by $\pi(n)$.
In this problem, you will be developing a code that computes $\pi(n)$.
First write a function Write a function Eratosthenes(n)
that lists all the prime numbers less than or equal to n
, by using the process of the Sieve of Eratosthenes as follows.
Once you've found the list of all the prime numbers less than or equal to $n$, you will be able to easily compute $\pi(n)$.
What is $\pi(1000000)$, the number of the prime numbers less than one million?
n=1000000
def Eratosthenes(n):
number = list(range(n+1))
isprime = list(range(n+1))
primenumbers = []
for i in number:
isprime[i] = 1
isprime[0], isprime[1] = 0, 0
k=2
while (k<=n):
if (isprime[k]):
primenumbers.append(k)
for j in range(2*k,n+1,k):
isprime[j] = 0
k += 1
return primenumbers
def prime_counting_function(n):
return len(Eratosthenes(n))
print(f'pi({n})={prime_counting_function(n)}')
pi(1000000)=78498