How do you calculate the amount of prime numbers less than or equal to N?

March 18, 2023

I want to write a program that determines the amount of prime numbers less than or equal to N (variable containing user input).
This is what I’ve got:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    for j in range(2, int(i/2)+1):
        if (i % j) != 0:
            primes += [i]
            count += 1

print(count)
print(primes)

But when I run the code, it doesn’t take the numbers 2 and 3 to be prime. How can I fix this program?

>Solution :

You can try these changes:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    is_prime = True
    for j in range(2, int(i/2)+1):
        if (i % j) == 0:
            is_prime = False
    if is_prime:
        primes += [i]
        count += 1
print(count)
print(primes)

To check if the number is prime, you need it to check if for ALL smaller numbers the remainder is different than 0.

Also, primes += [i] should be in external loop as you want to count every number at most once.

Note that this solution is far from optimal in terms of efficiency. Some improvements may be: