import time
import math

N = int(input("Please enter N: "))

sTime = time.time()
primes = [2, 3, 5]

if N < 5:
    print("N must be larger than 5")
    exit()
    
"""
This isPrime function assumes that (1) primes is a 
sorted list of prime numbers, and (2) the largest 
prime number in primes is larger than sqrt(n)
"""     
def isPrime(n):
    i = 0
    bound = int(math.sqrt(n) + 1)
    while primes[i] <= bound:
        if n % primes[i] == 0:
            return False
        i = i + 1
    return True


for i in range(6, N+1):
    if isPrime(i):
        primes.append(i)
  
print(f"Time to build the prime number list is {time.time() - sTime}")

print(f'Number of primes: {len(primes)}')