Question

I have questions, as do many it seems, regarding ps1a. I have compeleted the assignment, but two (and probably more) questions remain. 1. I am wondering why my primality test finds 2 as prime when the range is set as (2, int(n**0.5) + 1). When the square root of two is turned into an integer regardless of whether it is made a one or a two, shouldn't it divide with no remainder and not be counted as prime. The opposite seems to be the case in my working code. 2. I do not understand why the code is giving me problems when I try to eliminate the function and use nested loops. Here is that

Answer 1

Can you post your code to codepad.org so we can take a look at what you're doing?

Answer 2

Yeah my original post got cut off apparently, and I have been having a tough time trying to add a second to put in the link. Here is the link: http://codepad.org/Fd4oehOU Any ideas why the loop times out?

Answer 3

As far as my first question goes, it seems that my primality test should not find that 3 is a prime number either (but it does). When using either the trunc() or int() statements to make square roots an integer, the square root of 3, as with 2, is rounded down to 1. 3, like 2, should divide into 1 without a remainder and thus should (falsely) not be determined to be prime. Is it because 1 is less than 2 (the first number in the range of the for loop), and that somehow messes with the loop and causes it to "miscalculate" in those cases. I saw someone else who was getting the right answer post code a couple days ago that specifically had a statement if n == 2 return True within their for loop. This statement makes sense. It should also be required for the number 3. They purported to have working code, but did not have such a statement for the number 3. I cannot figure out for the life of me why this is happening. Sorry for the long post.

Answer 4

[This is the third fluttering time I'm typing this pellet!!!]

What does range (2, int(n**0.5) + 1) return when n is 2 or 3?

Add debug print statements right inside each loop to see what the values are. That should make everything clear.

Answer 5

dmancine: I checked and int(n**0.5) returns a value of 1 when n is 2 or 3 which would make the range (2, 2). Since the actual range is one less than the second "2," this would make a the range (2, 1). My question is, at least for the number 2, shouldn't this mean that the remainder would be 0 meaning that the test should find that two is not a prime number? My problem comes from the fact that the primality test actually finds that 2 is prime. I am confused as to why this is so. Here is my finished code so you can see better what I mean (spoiler alert for those still working on ps1a): http://codepad.org/bl6Ighx6

Answer 6

It appears that in python, when for loop is called for an empty list, it simply ignores the for loop and moves on to the next lines of codes. Thus, when n = 2, for loop is ignored and the next line, return True, is read. So Primality(2) and Primality(3) is returned True

Answer 7

for i in range(start, end):
What this is doing is first evaluating the range() function, which returns a list. Then it's iterating over the elements in that list, assigning each to i (just like for c in "abcd" or for k in [8, 6, 7, 5, 3, 0 , 9]).

So, my question still stands: what does range(2, int(n**0.5) + 1) return?

Answer 8

So, nothing happens. So lee832's response was correct. So, essentially, the second argument in the range function has to be larger than the first for it to work correctly? This is also means that its was sort of a fluke that 2 and 3 were determined to be prime I suppose.

Answer 9

Well, range(x, y) is a function which returns a list containing all the integers, n, such that x <= n < y. If y<=x, then no integers can satisfy that inequality, so it returns the empty list, [].

A for loop can loop over an empty list with no problem whatsoever. It simply loops 0 times. So the entire loop will be skipped. That's not a fluke, it's by design, and works in a very deterministic way.

As for why it detects 2 and 3. You tell it to check divisors from 2 to int(n**0.5)+1. For 2 and 3 there are no such candidate divisors, so it skips the loop entirely. So, you can't help but find no divisors of 2 or 3. Therefore, they are forced to be prime.

Think about it another way: What divisors would you want your code to test for 2 and 3?

Now, it may be a fluke that the code works this way for 2 and 3, even though you didn't specifically design it to work that way for these cases. And that's probably kinda true. But, you *did* design the code to work the proper way to determine the primality of *arbitrary* numbers. Why *shouldn't* it work for 2 and 3? They're just as arbitrary as any other numbers.

Having said all that, you were right to wonder about the behavior of the code for 2 and 3. In software testing these are called edge cases or boundary cases. A loop has a starting point and an exit condition. You think you coded them right, but you always think you code things right (why would you write code if you thought it was wrong?). So, you test it. And you don't just test the exit condition, you test a little before and a little after it, too, and you make sure it stops right when you expect it to. Same thing here. You're starting at 2, so make sure 2 and 3 work, because you might have gotten something a little wrong. (Incidentally, what does your code do for 0 and 1? Is that what you expected?)

Answer 10

When n is 0 or 1, the code treats them as prime. This is what I would expect now that I understand the range(x,y) function, as these two values for n will also result in an empty list when range is evaluated. This is not a problem for the code in this assignment since n starts at 2 when it first goes through the loop. However, if I were to modify the code to calculate whether a specific number taken from user input is prime, it could be problematic. I compensated for this by adding the following lines to my function prior to the for loop:

if n == 2 or n == 3:
return True
elif n == 0 or n == 1:
return False

When these two lines are added and the rest of the code is left intact, it still calculates the 1,000th prime number correctly, even if n starts at 0. Thanks for all the help.

Answer 11

Good. But the first test is unnecessary since you've already shown that the main body of the code does the right thing for 2 and 3.

(For anyone who doesn't know, 0 and 1 are considered neither prime nor composite.)