It's easy. If you can't divide a natural number N by any number less than that, then N is a prime number (of course you should take no account of 1 and N itself). For example, take 7. You can't divide it by 2, 3, 4, 5, nor 6. It means 7 is a prime number. (I'll use 'PN' for a 'prime number'.)
This is the most 'clear & easy' way to tell N is PN or not (as a matter of fact, the 'only' way to get prime factors of N ; all other methods are revisions of this method).
But you know it takes a very very very long time. You would say you need not divide N by all the numbers less than that, you need only to divide it by PNs less than N.
Yes, that's right. It will save your time. It sounds stupid to divide N by 4, 6, or 8 after you've tried by 2 (6, 9, or 12 after 3 ; 10, 15, or 20 after 5...). Take 101 to be N. You need try to divide N by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...89, and 97 (you try 25 times instead of 99, about one forth, and see you can't, so 101 is PN).
You would say again, why by 'PNs less than N' ? 'PNs less than the square root of N' will do.
That's right again. The square root of 101 is 10.5, then you only need try to divide N by 2, 3, 5, and 7. Only 4 times. Should I explain why ? If N is divided by PN x and PN y (N=xy), either x or y must be less than the square root of N. If both x and y is greater than the square root of N, then xy (=N) would be greater than N, and that is absurd. So N will be divided by 'PN(s) less than the square root of N' if it is not PN.In average, there supposed to be 6.87 PNs in arbitrary 100 continuous numbers (Ref : Emile BOREL, Les nombres premiers, Collection QUE SAIS-JE?, 1958). And there exists 455052511 PNs under 10000000000 (10th power of 10). Take N to be 100000000000000000000 (20th power of 10). The square root of N is 10000000000 (10th power of 10), and 455052511 numbers will be PNs (that is, you have to try 455052511 times to tell N is PN or not, if fortune is not on your side).
If we take N to be 155th power of 10 (the size of the key used by RSA cryptsystem), we must try about 6.87*(76th power of 10) at worst.
BTW, if we want only to tell N is PN or not (I mean if we put aside prime factors of N), the question is speeded up.
Get (N-1) powers of 2, and divide it by N. If the remainder is not 1, then N is not PN. Take 14. (14-1) powers of 2 is 8192. 8192 divided by 14 remains 2. Then, 14 is not PN.
N is not always PN if the remainder is 1, but we rationally may suppose it to be PN most of the case (the exception is one in a million). You only have to check Ns whose remainder is 1 whether it is really PN or not.
If you are a Mac user, AppleScript or HyperCard will help you. Ask HyperCard to "Answer 2^(N-1) mod N", if the answer is "1", then N should be PN (it will work while N is less than 16400).