PYTHON: Checking Primality of Integers
-
Goal: I want to better understand a snippet of code.
Experience: I am not an absolute beginner but I'm pretty new and have little experience. This is my first post on this website.
Problem: I don't understand why when the code checks for the primality of 2, it prints 2 as a prime number.
Background: A few days ago I decided that I wanted to be comfortable coding in python. I reviewed a lot of basic concepts that I had learned before so I would be more prepared to learn more complicated concepts. I finally came across an exercise that required me to find and print prime numbers. Below is the snippet of code that is slightly modified from a YouTube video.
lower = 2 upper = 100 for num in range(lower,upper+1): for i in range(2,num): if (num%i)==0: break else: print(num)
Here is also a link to the source of the code that I'm studying. If you are checking 2 for primality then in the code, when it comes to the modulus operation (num%i)==0, if it equals that, then supposedly you are dealing with a composite number. if my bounds were held in the natural numbers and greater than 2, the nested for loop will check for all of the numbers except for 1 and the number of interest, therefore checking for all possible factors. I'm under the belief that if the nested for loop does not find a number that is divisible by num, then the for loop will reach the end of the range and then execute the else component, which is to print num. In this case, the "num" is a prime number. The problem is that when the lower limit is 2, and I check num%i, this will translate numerically to 2%2, which equals 0. Because of this, I don't know how or why it prints the number 2 as a prime number. This doesn't happen with any other lower limit. If the lower limit is 3, then it checks 3%2, which isn't 0. In this case, the nested for loop ends at the first iteration and then the else statement is proceeded to be executed. However, clearly, if the code is executed, it absolutely prints all prime numbers, obviously including 2.
-
Ah! In that case: if
if (num%i)==0:is true even once it will not count num as a prime.In the case of 2 the inner loop
for i in range(2,num):never runs soif (num%i)==0:will never be true. This is because range(2, num) where num is 2 does not loop. So it considers 2 a prime.Please let me know if that is not clear enough and I will explain further.
-
I don't think a lot people realize that 2 is actually a prime number.
"A prime number is a whole number greater than 1 whose only factors are 1 and itself. A factor is a whole number that can be divided evenly into another number"
Given the definition above 2 meets that criteria.
Common mistake
-
First off, thanks for your friendly response. It's a breath of fresh air in comparison to StackOverflow.
Second, I probably incorrectly assumed that the average person did know, which looking back in retrospect, I too didn't know until I studied the fundamental theorem of arithmetic. Therefore I should have been more clear about that.Thirdly, the problem is that the code still prints 2 as a prime number, which is great but I don't understand why it prints it considering that the check for primes involves the modulus arithmetic and 2 modulus 2 is 0, which makes me think that the for loop should break out of the loop. The problem is that because of my small experience in coding, there is something in that code that I'm not understanding. Based on when I dissected the code, I believe that my confusion is related to the break statement.
-
Also, I'm unsure how to use some of code compilers that you've provided however I have tried codepen and don't think I can use it for python. With that being said, below is a link to a compiler that has my code. Perhaps this could be of help.
https://onlinegdb.com/rJs7ORYKU
-
Ah! In that case: if
if (num%i)==0:is true even once it will not count num as a prime.In the case of 2 the inner loop
for i in range(2,num):never runs soif (num%i)==0:will never be true. This is because range(2, num) where num is 2 does not loop. So it considers 2 a prime.Please let me know if that is not clear enough and I will explain further.
-
Thank you so much!! I understand your explanation perfectly. I already knew that when you look at range of something it includes (num-1), therefore it doesn't include the last integer. I simply incorrectly assumed that because in the "range(lower,upper)", because you had the lower defined as 2, that it would check it, even though the upper, in this case, 2, would not be considered. I should have known better because even I explained that if I checked 3 for primality, the for loop would only run once. Therefore, it would make sense that if I was checking 2, then the for loop wouldn't even run once. Thanks so much, I can finally work on something else like functions and get this program behind me.
-
Right. The upper range number can cause some confusion. I am glad I could be of help.
Do you mind selecting my answer as the correct one? Thank you and post anytime!
-
Of course! This might be a dumb question but where do you do that? It's just that I've been searching for several minutes with no success.
-
Oh sorry. I didn't realize this topic was not set as a question. So you would first have to set it to a question (which I did) and then mark my post as the right answer by clicking the three dots (more options).
-
ok, I understand now
