At 1/1/13 03:57 PM, FallingTears wrote:
Thanks for the response. Love the Zen!!! Anyway, could you explain to me a little more how the math in your code works. I have done square roots, but not as manually as that.
When I'm doing num**0.5 that's the exact same as sqrt(num). Raising a number to the 0.5th power will give you the number's square root (just to be clear: the ** operator in Python is the exponent operator).
The reason I am adding one to the result is essentially just error padding. If you did not do that and checked, for example, 8 for prime you would get the square root of 8, which is 2.82, which would be rounded down to 2 when converted to an integer, and then considered prime. 8 is of course not prime, so padding the result with a +1 will help prevent that error from occurring. Keep in mind that this only works this way because of how the for operator works in Python (because range(8) will iterate through 0 to 7, not including 8).
In short: it prevents false positives without producing false negatives.
kiwi-kiwi already explained why you only need to look up to the square root of a number to determine if it's prime, but I'll try explaining in my own words: basically if you take any number that is not prime, which I will call n, then any number between 1 and sqrt(n) will be divisible by something that's not 1 or n and anything that the square root of n can be divided by the number n itself can also be divided by.
Take the number 64, for example, which has a square root of 8. The number 8 is divisible by 1, 2, 4, and 8. The number 64 is also divisible by 1, 2, 4 and 8, which therefore means 64 is not a prime number.
But if you take the number 107, which is prime, and you produce its prime which is 10.34, and round that down and then increment by one, and you get 11. The number 11 is prime, therefore 107 is also prime.
That's the best I can explain it. :)