Can I use proper division concept for checking prime numbers? I am doing Problem 95 on Project Euler website here. The problem description stated that proper divisors of a number are all the divisors excluding the number itself. I want to know whether this concept can be used to check a prime number. Specifically, if the only proper divisor of a number (for example 13) is 1, can I, by all means, state that the number is a prime number?
 A: Yes, absolutely. It may not be the most computationally efficient way, nor the most philosophically elegant, but it may make more sense to you.
For the most part, you can match the divisors in pairs. For example, is 729 prime? It's not. We see that:


*

*$1 \times 729 = 729$ (but you already knew that)

*$3 \times 243 = 729$

*$9 \times 81 = 729$

*$27 \times 27 = 729$


731 is not prime either, since $17 \times 43 = 731$. But 733 is prime:


*

*$1 \times 733 = 733$ (obviously)

*$3 \times 244 = 732$, not 733

*$5 \times 147 = 735$, not 733

*...

*$25 \times 29 = 725$, not 733

*$27 \times 27 = 729$, not 733

A: You can cut your work down quite a bit.  If $n$ is a positive integer, and if $n$ contains no proper divisors that are between 2 and $\sqrt{n}$, then $n$ must be prime.  
The reason why you only need to check integers between 2 and $\sqrt{n}$ is because $n = \sqrt{n}*\sqrt{n}$, and so if $n = ab$ with $a,b$ integers both greater than 1, then at least one of $a$ or $b$ is less than or equal to $\sqrt{n}$.
