- #1
split
- 25
- 0
When trying to determine whether a number is prime or not, the following algorithm is often used: Test all numbers up to [sqrt[n]] ([x] is the ceiling of x) to see if any divide evenly into n. If any do, the number is not prime.
My question is, why do you only have to test up to [sqrt[n]]? How does that work mathematically?
My question is, why do you only have to test up to [sqrt[n]]? How does that work mathematically?