Похоже, о натуральных числах можно говорить бесконечно.
Сейчас я расскажу о «специфических» натуральных числах, называемых
простыми.
Простое число – это натуральное число, большее единицы, которое имеет ровно два делителя. Оно делится на единицу и на само себя.Именно вследствие такого жесткого определения сама единица не попадает в разряд простых чисел: у нее-то делитель только один: она сама.
Поэтому ряд простых чисел начинается с двойки.
Вот первые его члены:
2, 3, 5, 7, 11, 13, 17, 19, 23, …читать дальшеПонятие простого числа является основным при изучении делимости натуральных чисел.
Всем известно (проходят это в средних классах школы) что любое число, отличное от 1, можно единственным образом (с точностью до порядка множителей) разложить в произведение простых чисел.
Ну, например,
54=2*3*3*3
102=2*3*17
1000=2*2*2*5*5*5
Простых чисел бесконечно много. Это предложение называется теоремой Евклида, потому что ее доказательство приводится в знаменитых Евклидовых «Началах».
Алгоритм нахождения простых чисел называется решетом Эратосфена.
Состоит он в следующем.
Выписываем весь натуральный ряд, начиная с двойки:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,…
Число 2 – простое.
Зачеркиваем все натуральные числа, делящиеся на два, – просеиваем их, убираем из рассмотрения. Получим:
2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27,…
Число 3 – первое неотсеянное число после 2, – простое. Выбросим все числа, делящиеся на 3:
2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27,…
имеем:
2, 3, 5, 7, 11, 13, 17, 19, 23, 25, …
Число 5 – следующее неотсеянное число – будет простым.
Вычеркиваем всё, что делится на 5.
2, 3, 5, 7, 11, 13, 17, 19, 23, …
И так, пока хватит терпения. Будем получать все больше и больше простых чисел.
В книжке, которую я читала в детстве, было нарисовано сито, из которого сыпались четверки, восьмерки, девятки…
И описано было для детишек весьма и весьма доходчиво. Есть числа «чистые», – то бишь, простые, – и вся остальные – составные, которых медом не корми – дай только на что-нибудь поделиться. Трясем, трясем сито, отделяем зерна от плевел, – вся шелуха просыпается вниз. И вот они, – сияющие своим ослепительным блеском, – остались одни только простые числа. Жемчужины среди навоза. До меня ну никак не доходило, в чем их такая особая заслуга, но, наверное, не в последнюю очередь и поэтому, от непонимания, возникал такой божественный пиетет перед этим решетом, из которого сыплется числовой дождь…
И это еще не всё!
Никто не знает, как распределены в натуральном ряду простые числа. Есть ли закономерность? Нет ли? В среднем, при увеличении чисел, простые среди них попадаются более редко. И это всё, что математики могут сказать на сегодняшний день.
Существуют сколь угодно длинные отрезки ряда натуральных чисел, среди которых нет ни одного простого числа.
С другой стороны, встречаются даже ОЧЕНЬ большие простые числа, разность между которыми равна 2. Такие простые числа называются «близнецами».
До сих пор неизвестно, конечно или бесконечно множество таких близнецов.
Вот парочка из них (чрезвычайно громадных):
10 006 427 и 10 006 429.
Но и это еще не всё!
Есть такая неразрешенная доныне задача, которая носит название предположения Гольдбаха. Заключается это предположение в том, что любое четное число больше двух может быть представлено в виде суммы двух простых чисел.
Вот примеры:
6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 + 5, 12 = 5 + 7, 14= 3 + 11 = 7 + 7, и т.д.
Пока человечеству не удалось ни доказать это предположение в общем виде, ни найти хотя бы один контрпример.
А казалось бы – чего проще ))))
Простые числа...
@темы:
Натуральные числа,
простые числа,
Amicus Plato
-
-
10.11.2006 в 22:45-
-
10.11.2006 в 22:49-
-
10.11.2006 в 22:51За баллы — спасибо )))
Так а ты же тоже хотела про целые-дробные-...? Или как?
-
-
10.11.2006 в 22:54-
-
10.11.2006 в 22:54-
-
10.11.2006 в 22:58-
-
10.11.2006 в 23:01Если ни на что не разделится без остатка, значит -- простое )))
-
-
10.11.2006 в 23:03Minority есть. У меня друг на этих алгоритмах защищался
-
-
10.11.2006 в 23:09просто я как программист интересуюсь.
пока что осуществляла две реализации:
1. для каждого числа проверяла количество делителей перебором. Ну правда проверялись не все числа, а только до половины проверяемого числа.
2. решето Эратосфена как раз. Там работала со структурой множество. Есть в этой структуре большой минус6 на Паскале всего 256 возможно элементов в множество поместить. Т.е. одо множество в итоге получалось - простые числа до 256. Дальше можно еще создавать мнжества со следующими 256 числами... но это так муторно....
А на Си такого вообще нет, вот я и спросила, нет ли какого-то принципиально другого метода.
-
-
11.11.2006 в 15:59Вот, Лямбде наверняка тут есть, что рассказать ))))
-
-
11.11.2006 в 16:16-
-
11.11.2006 в 17:16