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.
