posted by kim on .
Which of these is a prime number?
407, 409, 411, or 413
how did you get that?
Suppose you are given some number N. If x<sqrt[N] then N/x will be larger than sqrt[N]. This means that any factor of N must be smaller than or equal to the square root of N. This follows because if N has a factor larger than the square root of N 8other than N itself), then after dividing N by that number you would get a number smaller than the square root of N (that number is then not equal to 1). However, that number you get upon division will be a divisor of N too. That then contradicts the assumption that N has only divisors larger than the square root of N.
So, what you do is you check all the prime numbers till the square root of N to see if they divide N.