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