Guido van Rossum

And we go all the way to, is it divisible by 9?

And it is not, well, actually 10 is divisible by 2, so there we stop, but say 11.

Is it divisible by 10?

The answer is no, 10 times in a row, so now we know 11 is a prime number.

On the other hand, if we already know that 2, 3, 5 and 7 are prime numbers, and you know a little bit about the mathematics of how prime numbers work, you know that if you have a rough estimate for the square root of 11, you don't actually have to check is it divisible by 4 or is it divisible by 5.

All you have to check in the case of 11 is, is it divisible by 2, is it divisible by 3?

Because take 12.

If it's divisible by 4, well, 12 divided by 4 is 3, so you should have come across the question, is it divisible by 3 first?

So if you know basically nothing about prime numbers except the definition, maybe you go for x from 2 through n minus 1 is n divisible by x.

And then at the end, if you got all no's for every single one of those questions, you know, oh, it must be a prime number.

Well, the first thing is you can stop iterating when you find a yes answer.

And the second is you can also stop iterating when you have reached zero.

the square root of n, because you know that if it has a divisor larger than the square root, it must also have a divisor smaller than the square root.

Then you say, oh, except for 2, we don't need to bother with checking for even numbers, because all even numbers are divisible by 2.

So if it's divisible by 4...

we would already have come across the question, is it divisible by two?

And so now you go, special case, check, is it divisible by two?

And then you just check three, five, seven, 11.

And so now you've sort of reduced your search space by 50%, again, by skipping all the even numbers it kept for two.

If you think a bit more about it, or you just...