Calculating prime numbers

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.

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.

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.