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.(adsbygoogle = window.adsbygoogle || []).push({});

My question is, why do you only have to test up to [sqrt[n]]? How does that work mathematically?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Prime number algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**