Question

Hi all. I have completed Problem 1 of Assignment 1. If anyone would like to offer a better solution, much appreciated.

http://codepad.org/RK36VF2f

Answer 1

I don't know if this is better or not. http://codepad.org/AbCEgJ0g
You do need to make some notation, though.

Answer 2

Also, you only need to generate the last integer.

Answer 3

Thanks for the feedback. Your code seems to be a little more streamlined, especially with the "xrange" function. I didn't know about that.

Answer 4

Oh yeah, somebody here clued me in to that. Remember, you only have to test up to the sqrt of n, and only odd numbers. That helped me cut down on complexity.

Answer 5

Forgive my math obtuseness, but why are you only testing up to sqrt(n)?

Answer 6

I will reformulate for clarity's sake: Even if there is a factor of a given N that's bigger than square root of N, then there is a factor of N that is smaller than the square root, because factor1*factor2*...*factorM will have to be equal to N. It's easy to see that if two factors are bigger than square root of N, than the product between these two is bigger than N, something that contradicts the first statement.
Example: 21. 7 is a divisor of 21 and is bigger than the ceil of square root of 21, but is divisible by 3 already, hence not prime.