Мы все когда-то изучали простые числа, вам сейчас любой пятиклассник (конечно, достаточно добросовестный, чтобы учить уроки) объяснит, что это такое, приведет парочку примеров и на коленке разложит какое-нибудь небольшое число на простые множители. А вот многие люди постарше наверняка уже не помнят такие фокусы, да и зачем? «Ерунда, опять какие-то школьные флэшбеки и знания, совершенно не нужные в жизни. Я этими вашими простыми числами нигде, кроме школы, не пользовался», - спешу заверить, пользовались и не раз...
Простые числа — это такие натуральные числа, которые делятся только на единицу и на самих себя (имеют только два делителя). Все остальные натуральные числа, которые имеют более двух делителей, называются составными. Единицу не относят ни к простым, ни к составным числам, т. к. у неё только один делитель — единица. Самое маленькое (и первое) простое число — 2.
Следующие по возрастанию простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ... Ещё Евклид доказал, что множество простых чисел неограниченно,...