Prime Numbers

Most of integer numbers could be represented as product of several smaller integers, for example:

8 = 2 * 4 = 2 * 2 * 2
100 = 10 * 10 = 20 * 5 = 50 * 2 = 2 * 2 * 5 * 5

However some integers could not be produced in such way. I.e. they are not divisible by any integers (except, of course, 1 and itself). They are called Prime Numbers.

It is easy to discover several smallest of such integers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Obviously all of them except 2 are odd since all even values are divisible by 2.

At first glance the property of being prime (i.e. primality) looks like a curious mathematical trifle. But as a matter of fact prime numbers are extremely important. Most algorithms of modern cryptography heavily employ either prime numbers or values related to them. And we know that cryptography nowadays is of great importance in communications and especially in military communications and control.

Non-prime integers are called composite. It can be proven that any composite number could be represented as a product of a set of primes in unique way. Refer to Fundamental Theorem of Arithmetics for explanation.

Generation of Primes

There is no simple way to check if some arbitrary value is prime (that is one of the facts which make them valuable).

Algorithms suitable for novice programmers rely on consecutive checking the whole row of numbers up to the value in question. Let us study most common of them.

1. Create a list (or array with additional pointer to keep the index of the "end") to store primes found so far.
2. Put value 2 to this list.
3. Iterate through all odd numbers from 3 to n (which we want to check) and for each value m of them:
   • try to divide the current value by every of the primes from the list, starting from smallest;
   • if divisor is found (i.e. remainder of any division is 0) the current number is composite and we skip it;
   • otherwise, if no prime divisor found, the current number is prime itself and is added to the end of list.

Important that divisibility for any m needs to be checked only with primes less than sqrt(m) - i.e. the inner loop processing values from list in the step 3. of algorithm above should stop when currently inspected prime p satisfies condition p * p > m. Also if we want to check only value n for primality, we can jump to it in our external loop (step 1.) as soon as m becomes so big that m * m > n. This idea allows to decrease the amount of iterations and speed up the algorithm dramatically.

We do not give a proof for this fact - it is recommended as a good mental exercise for you. Could you at once guess why greater primes (larger than sqrt(n)) are not interesting if we checked all of the smaller ones?

Example

Suppose we already found ten first primes shown above (from 2 to 29) and want to find the next few primes:

• we take 31 and try to divide it by 2, 3, 5 - none is succsessful; we can stop then since the next prime is too large (7 * 7 = 49 > 31) and pronounce 31 to be prime;
• for 33 we try to divide it by 2 and 3 and found it divisible by latter (33 = 3 * 11), so it is composite;
• next value, 35 is tried by 2, 3, 5 and is found composite too (35 = 5 * 7) - well, it was obvious since in decimal representation all numbers ending with 5 or 0 are divisible by 5;
• value 37 is not divisible by any of 2, 3, 5 and is another prime;
• so we add 41, 43, 47 to the list of primes;
• when we get to 49 it appears the first number for which we should try more numbers: 2, 3, 5, 7 - well, it is composite (49 = 7 * 7);
• value 51 is found to be divisible by 3 - it is composite;
• value 53 is not divisible by any of 2, 3, 5, 7 - it is prime;
• so we can check all numbers up to 121 using only these four smallest primes (because 11 * 11 = 121).

Wonderfully, with so few primes (from 2 to 31 for example) we can test for primality anything up to 1000 (even somewhat further), because the next prime 37 gives the limit of 37 * 37 = 1369.

Sample Tasks on Prime Numbers

• Prime Numbers Generation
• Integer Factorization
• Prime Ranges