Простые числа. Таблица простых чисел.

Простые числа. 

Простое число — это натуральное число, которое больше единицы и не имеет других делителей кроме единицы и самого себя. Остальные натуральные числа, кроме единицы, называются составными и имеют делители, отличные от единицы и самого себя.

 

Натуральное число 1 не является ни к простым, ни к составным числам и имеет единственный делитель 1, т.е. делится только само на себя.

Основная теорема арифметики

Любое натуральное число может быть представлено в виде произведения простых чисел единственным образом ( с точностью до перестановки): ​\( a=d1​· d2​·..​·dn \)​, где  ​\( a\in N \), ​\( d1,d2,…,dn \)​— простые числа.

Каноническое разложение числа на простые множители — это произведение, в котором множители упорядочены по возрастанию:

\( a=d1​· d2​·..​·dn \),

где  ​\( a\in N \), ​\( d1<d2<…<dn \)​— простые числа. 

 Примеры:

​\( 55=·5·11 \)​
​​\( 110=2·5·11 \)​
​\( ​210=2·3·5·7 \)​

Важно знать:

1. Различные представления одного и того же составного числа в виде произведения простых чисел различаются только порядком множителей:

   Примеры:

   ​\( 90=2·3·3·5=2·3^2·5 \)​ — каноническое разложение
   ​\( 90=3·3·5·2 \)​
   ​\( 90=3·5·2·3 \)​

2. Разложением простого числа на простые множители считается само это число:​\( 17=17 \)​.
3. Простых чисел существует бесконечно много.
   Пусть p —  самое большое число, а 2, 3, 5, .., p — все простые числа.

   \[ a=2·3·5·7·11·…·p+1 \]

   
    Число ​\( a \)​ больше всех все простых чисел 2, 3, 5, .., p.  При делении на любое из них число а дает остаток, равный 1. Следовательно, число ​\( a \)​ — простое, так как не делится ни на одно простое число, меньшее а.
4. Из основной теоремы арифметики и свойств делимости следует:  если в разложении числа на простые множители отсутствует какое-то число, например, 3, то исходное число не делится на 3 и на все числа, кратные 3:

   Пример:
   ​\( 70=2·5·7 \),
     70 делится на 2, 5, 10, 7, 14, 35, но не делится на 3 и числа, кратные трём.

   Если в разложении числа  a на простые множители отсутствует какое-то число b, то  a  не делится на b, нельзя представить а в виде ​\( a=nb \)​

Как проверить, является ли число простым?

1.  Любое натуральное число можно представить в виде произведения простых множителей по основной теореме арифметики. Следовательно,  чтобы проверить, что число простое, достаточно проверить, что оно не делится на все простые числа, которые меньше него.

   Пример: Число 17.
   Простые числа, которые меньше 17:  {2, 3, 5, 7, 11, 13}.
   17 не делится ни на одно из этих простых чисел, следовательно 17 — простое число.

   1. Выписать все простые числа, которые меньше заданного числа ​\( a \)​.
   2. Если ​\( a \)​ делится хотя бы на одно число из списка, то оно — составное.
   3. Если ​\( a \)​ не делится хотя бы на одно число из списка, то оно — простое.

2. Можно уменьшить количество простых чисел нужных для проверки: взять только те простые числа, квадраты которых меньше исходного числа.

   Доказательство:
   Пусть​ \( a \)​ — составное, может быть представлено в виде произведения простых сомножителей b и c, отличных от 1 и ​\( a \)​:​

   \( a=b·c \)​
   ​\( a·a = (bc)·(bc) = (bb)·(cc) = b^2 ·c^2 \)​
   Следовательно, у каждого составного числа всегда существует делитель, отличный от 1, квадрат которого меньше этого числа. Если число не делится ни на одно из этих простых чисел, то оно простое, иначе — составное.

   Пример: число 17: 
   квадраты простых чисел​ {2,3}: \( 2^2 = 4 \)​ и ​\( 3^2=9 \)​ меньше 17;
   17 не делится на 2 и 3, следовательно, 17 — простое число.

   1. Выписать все простые числа, квадраты которых меньше заданного числа ​\( a \)​.
   2. Если ​\( a \)​ делится хотя бы на одно число из списка, то оно — составное.
   3. Если ​\( a \)​ не делится хотя бы на одно число из списка, то оно — простое.

Таблица простых натуральных чисел (до 1000)

	3	5	7	11	13
17	19	23	29	31	37
41	43	47	53	59	61
67	71	73	79	83	89
97	101	103	107	109	113
127	131	137	139	149	151
157	163	167	173	179	181
191	193	197	199	211	223
227	229	233	239	241	251
257	263	269	271	277	281
283	293	307	311	313	317
331	337	347	349	353	359
367	373	379	383	389	397
401	409	419	421	431	433
439	443	449	457	461	463
467	479	487	491	499	503
509	521	523	541	547	557
563	569	571	577	587	593
599	601	607	613	617	619
631	641	643	647	653	659
661	673	677	683	691	701
709	719	727	733	739	743
751	757	761	769	773	787
797	809	811	821	823	827
829	839	853	857	859	863
877	881	883	887	907	911
919	929	937	941	947	953
967	971	977	983	991	997