Another exercise from Python for Everyone, p4.17 page 209 of the first edition:
Write a programme that prompts the user for an integer and then prints out all prime numbers up to that integer. For example, when the user enters 20, the programme should print:
2
3
5
7
11
13
17
19
Recall that a number is a prime number if it is not divisible by any number except 1 and itself.
# Compute and display all of the prime numbers up to an integer entered by
# the user.
#
from math import sqrt
# Read the upper limit from the user.
limit = int(input("Enter an integer: "))
# Check each integer from 2 to limit, displaying it if it is prime.
for num in range(2, limit + 1) :
isPrime = True
# Check each number up to sqrt(num) to see if it divides into num.
for factor in range(2, round(sqrt(num)) + 1) :
if num % factor == 0 :
isPrime = False
if isPrime :
print(num)
I’d like clarification on the second for block. I hand trace the code following these columns: limit, num, isPrime and factor and try it entering 4, limit is 4, num is 2, isPrime false and factor 2. In the second for, testing the if, in this case i would have 2 % 2 so prime is set to false. But 2 is a prime number. And it gets printed as if the condition was set to True.
in range(2, round(sqrt(num)) + 1) - if num is 2, then this expression becomes in range(2,2) because sqrt(2) is 1.4…
I don’t know Python, but isn’t range(a,b) all integers starting at a and going up to but not including b? So (2,2) is all numbers starting at 2, up to but not including 2? - could that cause a problem?
Also, in the prime number test, the square root of the number to be tested is used as the upper limit of the values to be tested and should never be equal to the number itself. For example, you would test up to (but not including) 5 to see if 24 is a prime number because all the factors above 5 will be paired with a factor below 5. So this test won’t work with 2.
In the for-loop, they are setting isPrime to False as a default (ie unless shown otherwise, the number is not a prime). Then they do the prime number test, and if it works, they change isPrime to True.
At the end, if isPrime is a short way of saying if isPrime is True, and if that is the case, the number is displayed. (Disclaimer: I do not know Python, but this structure is common to many languages).
My question is below the code I pasted. When I hand trace the code, 2 is a prime number, but in the second for loop, if 2 % 2 == 0, then isPrime is False, when it’s in fact true. Sorry, it may be a silly question.
I’m probably just not explaining things clearly. For the number 2, this code is using 2 as the factor to test, but according to the definition of a prime number, you should not be testing the number itself as a factor, or you will always get False. Every number, whether prime or not, has itself as a factor.
So you need to add something to the code to check that sqrt(num) + 1 is less than the number being tested, or just start your prime test on numbers greater than 2.