Простые числа
Что такое простые числа, для тех кто не знает поясняю.
Простое число это такое положительное число, которое делиться только на себя и на единицу.
Примеры простых чисел до 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Существует алгоритм нахождения простых чисел предложенный Эратосфеном (275-194 до н.э., Греция), который разработал 'сито', чтобы найти простые числа.
Сито, как фильтр, который используется для фильтрации всех чисел, в результате чего остаються только простые числа.
По методу решета Эратосфена, чтобы найти простые числа до 100, нужно сделать схему натуральных чисел. Возьмем на примере числа от 1 до 100:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Шаг 1. Нужно вычеркнуть все числа кратные 2, т.е. каждое 2 число начиная с 4.
Шаг 2. Нужно вычеркнуть все числа кратные 3, т.е. каждое третье число начиная с 3. Возможно некоторые числа уже будут вычеркнуты, такие как например 6, т.к. оно было кратно 2.
Кажый 4 вычеркивать не нужно, т.к. мы их уже вычеркнули когда вычеркивали 2.
Шаг 3. Далее нужно вычеркнуть все числа кратные 5, т.е. каждое пятое число начиная с 5. Возможно некоторые числа уже будут вычеркнуты, как и в прошлом случае.
И так далее…
Нужно продолжать это делать, пока все номера до 100 не будут вычеркнуты.
Таким образом оставшиеся номера и будут простыми числами.
Списки простых чисел от 0 до 21 000 000 можно посмотреть здесь: