Why do we check up to the square root of a number to determine if the number is prime?
If a number n is not a prime, it can be factored into two factors a and b: n = a * b Now a and b can’t be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in … Read more