Prime numbers

Numbers that only divide by themselves, for example 7, 11, 13 - prime numbers. People have noticed long ago that numbers come in two different varieties. For example, number 12 can be divided without a remainder on 2, 3, 4 and 6. And the next number 13 is divided by itself: 13/13 = 1. In addition, each number is divided into one. Numbers such as 12 or 15, which can be divided into some other, smaller, are called compound. The smallest prime number is 2. The first primes were Eratosthenes (the so-called "Eratosthenes sieve"), as a table, and noticed that many prime numbers are grouped into pairs of twins: these are 11 and 13, 29 and 31, 41 and 43. The smallest A complex or complex number (except 1) is 4.

Numbers that only divide by themselves, for example 7, 11, 13 - prime numbers

The basic theorem of arithmetic asserts that each natural number, greater than one, can be represented as a product of primes, and by the only way up to the order of the order of the factors. Thus, prime numbers are elementary "building blocks" of natural ones. The representation of a natural number in the form of a product of simple numbers is called a simple factorization or factorization of the number.

Simple numbers can be found with the help of the "sieve of Eratosthenes", "sundara sieve" and "sieve Atkin". In practice, instead of getting a list of prime numbers, you often need to check whether the given number is simple. Algorithms that solve this problem are called tests of simplicity. There are many polynomial tests of simplicity, but most of them are probabilistic and are used for the needs of cryptography.

The largest known prime number as of August 2014 is 257885161 - 1.

Tools