Prime numbers are called those integers which are not divided without the rest into any other number, except unit and themselves. Due to various reasons they from antiquity interested mathematicians. It led to development of different ways of check whether the set number is prime.
Instruction
1. As the prime number by definition should not be divided on any another, except, an obvious way of check of number into simplicity — attempt to divide it without the rest into all numbers, smaller it. This way is usually chosen by creators of computer algorithms.
2. However search can be rather long if, say, it is necessary to check number of a view for simplicity 136827658235479371. Therefore it is worth paying attention to the rules capable to considerably reduce time of calculations.
3. If the composite number, that is represents the work of simple factors, then among these factors surely there has to be at least one which will be less square root from the set number. The work of two numbers, each of which is more than square root from some X, there will be obviously more than X, and these two numbers cannot be its dividers in any way.
4. Therefore even at simple search it is possible to be limited to check only of those integers which do not exceed the square root from the set number which is rounded up. For example, checking number 157, you touch possible multipliers only from 2 to 13.
5. If you have near at hand no computer, and the number should be checked for simplicity manually, then and simple and obvious rules come to the rescue here. Most of all you will be helped by knowledge of already known prime numbers. To check separately the divisibility on composite numbers is not present sense if it is possible to check divisibility for their simple multipliers.
6. The even number by definition cannot be prime as is divided into 2. Therefore if the last figure of number of a chetn, then it is obviously compound.
7. The numbers which are divided into 5 always terminate in the five or zero. The view of the last figure of number will help to eliminate them.
8. If the number is divided into 3, then and the sum of its figures too surely is divided into 3. For example, the sum of figures of number 136827658235479371 is equal to 1 + 3 + 6 + 8 + 2 + 7 + 6 + 5 + 8 + 2 + 3 + 5 + 4 + 7 + 9 + 3 + 7 + 1 = 87. This number is divided into 3 without the rest: 87 = 29*3. Therefore, and our number is divided into 3 too and is compound.
9. Also the criterion for divisibility on 11 is very simple. It is necessary to subtract the sum of all its even figures from the sum of all odd figures of number. The parity and oddness is defined by the account since the end, that is from units. If the turned-out difference is divided into 11, then and all set number is divided into it too. For example, let number 2576562845756365782383 is given. The sum of its even figures is equal to 8 + 2 + 7 + 6 + 6 + 7 + 4 + 2 + 5 + 7 + 2 = 56. Sum of odd: 3 + 3 + 8 + 5 + 3 + 5 + 5 + 8 + 6 + 6 + 5 = 57. The difference between them is equal to 1. This number is not divided into 11 and consequently, 11 is not a divider of the set number.
10. It is possible to check divisibility of number for 7 and 13 in the similar way. Break number into the three of figures, since the end (so do at typographical record for convenience of reading). Number 2576562845756365782383 turns into 2,576,562,845,756,365,782,383. Summarize the numbers standing on odd places and subtract from them the sum of numbers on even. In this case you receive (383 + 365 + 845 + 576) - (782 + 756 + 562 + 2) = 67. This number is not divided neither into 7, nor on 13, so and they are not dividers of the set number.