Jump to content

Menu

XWhy Does Divide by Primes Less Than the Square Root Trick Work?


Recommended Posts

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:

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...