Crimson Wife Posted September 5, 2012 Share Posted September 5, 2012 We are reviewing prime numbers today and I can't find an explanation for why when trying to determine whether a given number is prime or composite, you divide by all the prime numbers smaller than the square root. For example, when trying to determine whether 229 is prime, you divide by all the primes less than 15 (since the square root of 229 is slightly larger than 15). Why does this trick work? :confused: Quote Link to comment Share on other sites More sharing options...
regentrude Posted September 5, 2012 Share Posted September 5, 2012 We are reviewing prime numbers today and I can't find an explanation for why when trying to determine whether a given number is prime or composite, you divide by all the prime numbers smaller than the square root. For example, when trying to determine whether 229 is prime, you divide by all the primes less than 15 (since the square root of 229 is slightly larger than 15). Why does this trick work? :confused: Let's say the number has two factors, one big and one small. The small one will be less than the square root, the big one will be more than the square root (only if the number is a perfect square, it has two equal factors, which are the square root.) So, if I test all numbers up to the square root, I have tested all the smaller factors of all pairs of factors. If I can not find a factor smaller than the square root, no pair of factors exists - and I do not need to test the bigger factors, because they must have a smaller partner, whose existence I have already excluded. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.