Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime number algorithm

  1. Jul 30, 2004 #1
    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?
  2. jcsd
  3. Jul 30, 2004 #2
  4. Jul 31, 2004 #3


    User Avatar
    Science Advisor
    Homework Helper

    If an integer n is composite, then you can factor it n=ab where a and b are both integers greater than 1. We can't have both a>sqrt(n) and b>sqrt(n), otherwise we'd get n>n. If a<=sqrt(n) then any prime dividing a (and we know there's at least one) is a prime factor of n that's less than sqrt(n). If b<=sqrt(n), we likewise get a prime factor of n less than sqrt(n). So if n is composite, it always has a prime factor <=sqrt(n), and it's enough to check these to verify whether n is composite or not.
  5. Aug 1, 2004 #4
    Furthermore, you don't have to test every number up to the sqrt(n), just 2 and all of the odd ones.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook