I have a program which determines if a number is prime or not. The basic algorithm simply checks for the number being divisible by 1 and itself.

My question is, is there an upper limit to checking numbers for divisibility without a remainder? If yes, can you explain why?

My "gut" feeling is that any number above 1/2 the number being checked should be ignored, but I can't prove it.

  • 15
    $\begingroup$ Actually testing up to $\sqrt{n} \ll n/2$ (for $n \gt 2$) is good enough (there are certainly much cleverer things to do). Note that if $n = pq$ then either $p \leq \sqrt{n}$ or $q \leq \sqrt{n}$. $\endgroup$ – t.b. Apr 25 '11 at 20:09
  • $\begingroup$ @Theo Buehler - Thanks for the tips. $\endgroup$ – P.Brian.Mackey Apr 25 '11 at 20:23
  • 2
    $\begingroup$ You're welcome. Maybe you want to check out the Wikipedia page on primality tests. I'm sure that our local expert Bill Dubuque would have a lot more to say about this. I suspect that any decent library has much better methods implemented than any of the ones you could come up with yourself. $\endgroup$ – t.b. Apr 25 '11 at 20:31

I will try to explain by using an example.

Let's check if $37$ is a prime number.

  • It's obviously not divisible by $2$,
  • it's not divisible by $3$ (because $3+7=10$ which is not divisible by $3$),
  • and it's not divisible by five (because the last digit is not $0$ or $5$).

These are all the possible candidates for factors of $37$, and I will try to explain why. If $7$ is a factor of $37$ (which would mean that $37$ is divisible by $7$, and hence not a prime) then the other factor must be greater or equal to $7$, since we have already shown that there is no factor less than $7$. But $7 \cdot 7 = 49 > 37$. Then there is no point in trying with greater factors, because then the product would have to be even larger.

So we have shown that for $37$, we only have to try to divide by $2$, $3$ and $5$. As both Raeder and Theo has pointed out we don't have to go higher than the square root of the number we want to check, and I hope that my example will help explaining why.

Edit: As Picakhu suggested, I will explain why these methods for checking divisibility by $2$, $3$, and $5$ works.

Checking divisibility by $2$ and $5$
When checking for divisibility by $2$ or $5$, it is sufficient to check that only the last digit is divisible $2$ or $5$ respectively. This has to do with the fact that we are using $10$, which is the product of $2$ and $5$, as our base. I will explain using three-digit numbers. The explanation would be very similar if we had used more digits. All numbers $abc$ (where $a$ is the first digit, $b$ the second, and $c$ the third) can be written on the form $$abc = a\cdot 10^2 + b\cdot 10^1 + c\cdot 10^0 = a \cdot 100 + b \cdot 10 + c.$$ The notation I'm using can be confusing. To clear up: If, for example, $a=b=c=4$, then $abc = 444 \neq 4\cdot 4\cdot 4$. Let's see what happens if we divide by 2. $$\frac{abc}{2} = \frac{a \cdot 100}{2} + \frac{b \cdot 10}{2} + \frac{c}{2} = a \cdot 50 + b \cdot 5 + \frac{c}{2}$$ We notice that this is a whole number if and only if $\frac{c}{2}$ is a whole number, no matter what $abc$ is. We get a similar result if we divide by $5$. $$\frac{abc}{5} = a \cdot 20 + b \cdot 2 + \frac{c}{5}$$ Hence it is sufficient to check the last digit.

Checking divisibility by $3$
When checking for divisibility by $3$, it is sufficient to check that the sum of the digits is divisible by $3$. This is easiest to show using modular arithmetics. Keep in mind that $10 \equiv 1 \pmod 3$. If we use our three-digit number $abc$ again we see that $$a \cdot 10^2 + b \cdot 10 + c \equiv a \cdot 1 + b \cdot 1 + c = a + b + c \pmod 3.$$ Hence $abc$ is divisible by $3$ if and only if $a + b + c$ is divisible by $3$.

Wikipedia has a list of more divisibility tests like these.

  • 2
    $\begingroup$ Good answer @Eivind, but perhaps you would want to talk about WHY checking sum for 3, checking last digit for 5,2 etc work. It all comes to modular arithimatics, but there are other ways to check if a number evenly divides another especially if software is used. $\endgroup$ – picakhu Apr 25 '11 at 20:57
  • $\begingroup$ @picakhu: Thanks! The explanation of how to check divisibility with different numbers, wasn't really the objective for my post. On the other hand, it is an interesting topic, so maybe I should explain a little deeper. I'll see what I can do! $\endgroup$ – Eivind Apr 26 '11 at 7:04

First, I guess you been divisible only by 1 and itself.

For the actual question, you only need to check for factors up the square root of the number, since by then you will have found all possible products less than your given number.

By the way, your gut feeling is correct, since twice something larger than half your number will be larger than your number.

If anything is unclear, I'd be glad to clarify.

EDIT: I see that Theo has explained why this is true in a much clearer fashion in the comments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.