Advertisements
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:
- iterate
j
only up tomath.sqrt(i)+1
- break the inner loop as soon as you find the number is not prime
- use Sieve of Eratosthenes