[Python] Is there a way to rewrite this code so that it doesn't time out? This is on...

My code needs to be able to count the number of prime numbers less than or equal to the input.

Some examples:

count_primes_less_than(34) = 11
count_primes_less_than(69) = 19
count_primes_less_than(420) = 81
count_primes_less_than(666) = 121


All the tests will be with 1 ⩽ n ⩽ 10^10

Code length limited to 3000 characters to avoid hard coding.

Currently, I have this:

def count_primes_less_than(n:int) -> int:
L = 0
for i in range(2, n):
if is_prime(i):
L +=1
return L

def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True


It return the right values for all tests, but it keeps timing out.

Any answers need to return not a list of primes, but the number of primes below the given number.

Continue reading...