Тест простоты. Похож на решето Эратосфена, но экономичнее.

[феодора]

© Автор Бутарева Людмила
27 декабря 2006 г.

ОПРЕДЕЛЕНИЕ ПРОСТОТЫ ЧИСЕЛ

Все простые числа, кроме чисел 2 и 3, соответствуют формулам (6n -1) и (6n +1).
1. Запишем числа формулы (6n -1) от 5 до наибольшего числа, которое мы хотим протестировать на простоту, слева от значка [х]. Запишем числа формулы (6n +1) от 7 до наибольшего числа, которое мы хотим протестировать на простоту, справа от значка [х].

53 47 41 35 29 23 17 11 5 х 7 13 19 25 31 37 43 49 55

2. Первое от [х] слева число 5 – простое. От 5 влево и вправо отсчитываем каждое 5-ое число и отмечаем значком [х]

53 47 41 х 29 23 17 11 5 х 7 13 19 х 31 37 43 49 х

3. Следующее по величине неотмеченное число 7 – простое. От 7 влево и вправо отсчитываем каждое 7-е число и отмечаем значком [х]

53 47 41 х 29 23 17 11 5 х 7 13 19 х 31 37 43 х х

4. Все неотмеченные числа – простые. Достаточным является отмечаемое число [корень квадратный из наибольшего квадрата числа в ряду]. Для данного ряда чисел уже после вычеркивания каждого 7-го числа ( наибольщий квадрат числа в ряду 7^2 = 49 ) все составные числа получаются вычеркнутым.

[e2e4]

Хехе, вы просто заведомо (на этапе рисования решета) исключили из него числа кратные 2-м и числа, кратные 3-м, т.е. все числа, "вычеркиваемые" простыми числами 2 и 3. А то, что вы расположили остальные числа справа и слева некотой точки, на мой взгляд, не уменьшает трудозатрат алгоритма на вычеркивание остальных простых.

[RIP]

А мне модификация понравилась.
Конечно, в прикладном плане она ничего не дает (не в обиду будет сказано), но меня интересует исключительно "чистая" математика, и чихать я хотел на какие-то приложения.
На мой взгляд, очень симпатичная модификация. Неужели раньше никто не замечал?

[феодора]

Да, я действительно удалила числа, кратные 2-м и 3-м, сразу исключив из ряда 2/3 чисел, заведомо составных. Таким образом,на старте имеем дело с 1/3 чисел от решета Эратосфена.
При рассчете ряда от 2 до 55 Эратосфен зачеркнул кратные
2-м - 26 чисел
3-м - 16
5-и - 7
7-и - 1
-------------
итого: 50 чисел ( из них 15 повторно)

Я при расчете того же ряда простых чисел зачеркнула кратные:
5-и - 3 числа
7-и - 2 числа
----------------
итого: 5 чисел ( из них 2 повторно)

А лучше всего - я приглашаю проверить самим, насколько это быстрее.

[e2e4]

Идея сразу(при построении) вычеркнуть из решета числа, кратные некоторым простым - очевидна. Но такое решето по сути сводится к обычному решету, в котором уже обычным образом вычеркнулись кратные данным простым. Другое дело, что при обычном вычеркивании чисел из решета, трудоемкость уменьшается (каждое следующее простое вычеркивает все меньше чисел из решета, состоящего из конечного кол-ва чисел). В случае же построения решета, из которого заведомо вычеркнуты некоторые составные числа, мы должны знать:
1) Простые числа, которым они кратны. Как их найти в общем случае?
2) Трудоемкость вычеркивания чисел одинакова (или даже возрастает) при возрастании простого числа, кратные которому мы вычеркиваем.
3) Да, в случае попытки применить алгоритм решета Эратосфена на компьютере, сэкономится память. Обычно для простоты сразу исключают числа, кратные 2-м, как наиболее простое и очевидное решение.

Если речь идет об усовершенствовании алгоритма Эратосфена, и мы ограничимся только числами, кратными 2-м и 3-м, которые вычеркнем на старте, то да, ваш вариант будет быстрее. Но алгоритм решета далеко не самый быстрый и оптимальный, и перспективен (с моей точки зрения) только как ключ к пониманию простых чисел, т.е. в теории. На практике есть гораздо более быстрые и оптимальные алгоритмы. Если же вы попытаетесь далее усовершенствовать решето, и будете вычеркивать числа, кратные 5, 7,... на старте, то, боюсь, никакого выигрыша далее не получите.

[феодора]

RIP писал(а):

На мой взгляд, очень симпатичная модификация.

Спасибо. Она мне тоже нравится.

[RIP]

феодора
Ваш тест, действительно, работает быстрее решета Эратосфена. Но на практике приходится иметь дело с числами порядка, скажем, $10^{100}$. Для таких чисел ни решето, ни Ваша модификация абсолютно неприменимы. Конечно, я не знаток алгоритмической теории чисел, но думаю, что не сморозил огромную глупость.

[феодора]

e2e4 писал(а):

В случае же построения решета, из которого заведомо вычеркнуты некоторые составные числа, мы должны знать:
1) Простые числа, которым они кратны. Как их найти в общем случае?
2) Трудоемкость вычеркивания чисел одинакова (или даже возрастает) при возрастании простого числа, кратные которому мы вычеркиваем.
.

1)Здесь ничего искать не надо. Надо просто механически вычеркнуть ( для ряда 2 - 125):

Каждое 5-е число от числа 5 ( это: 35, 65, 95, 125 слева и 25, 55, 85, 115 справа).
Каждое 7-е число от числа 7 ( это:35, 77, 119 слева и 49, 91справа)
Каждое 11-е число от числа 11 ( это 77 слева и 55, 121 справа)

Все. Рассчет закончен. Вычеркнуто всего 16 чисел. Остальные - простые.

Если Вы поставили себе задачу найти именно кратные числа, а не простые, то:
Каждое 5-е кратно 5-ти, (см. выше), каждое 7-е кратно 7-ми, каждое 11-е кратно 11-ти.

2) При возрастании простого числа трудоемкость снижается. Например, числа, кратные 5-ти, в нашем ряду высеркнуты 8 раз, а числа, кратные 11 - только 3 раза.

Добавлено спустя 19 минут 17 секунд:

e2e4 писал(а):

Если же вы попытаетесь далее усовершенствовать решето, и будете вычеркивать числа, кратные 5, 7,... на старте, то, боюсь, никакого выигрыша далее не получите.

Если я начну вычеркивать на старте еще и числа, кратные 5 и 7, мне придется вести рассчет по 68-ми направлениям, а не по 2-м, как сейчас. А дальше - еще страшнее. Оптимальное сокрашение - это то, которое я сделала.
Кроме того, это не просто вычеркивание чисел на старте, это другой ряд чисел, с другими законами, которые позволяют делать подобные рассчеты.

[cepesh]

Порядок сложности тот же самый, что и у решета Эратосфена. По большому счету нет разницы, 3000 часов работает программа или 1000

[RIP]

cepesh
Рискуя оказаться забаненным , всё-таки возражу. Между 1000 часов и 3000 часов есть разница. Но между $3\cdot10^{10}$ часов и $10^{10}$ часов разницы, действительно, никакой.

[феодора]

RIP писал(а):

феодора
Но на практике приходится иметь дело с числами порядка, скажем, $10^{100}$. Для таких чисел ни решето, ни Ваша модификация абсолютно неприменимы.

На практике (действительно на практике, в криптографии) нужны не такие сумасшедшие числа, как нам пытаются внушить некоторые американские сайты. Истина, как всегда, лежит посередине. А у них это - отвлекающие маневры. Я, конечно, не хочу разрушать защиту банковской системы, но ... научное любопытство, знаете ли.

[cepesh]

RIP
Ну Вы же поняли мысль.
Как-то вы, кхм, "гуманитарно" смотрите на технические проблемы. Но желание мыслить нельзя оставить без поддержки. Так что успехов!

[RIP]

cepesh
В качестве примеров можно привести, например, док-во несуществования конечной проективной плоскости порядка 10 или док-во теоремы о 4 красках. Эти док-ва были получены с помощью компутера, причем время работы в этих задачах было поболее 1000 часов, если не ошибаюсь. Если бы удалось сократить его втрое(!), то было бы хорошо.
Но мысль я понял.
Прошу прощения за откровенную наглость и оффтопик. Больше не буду. (Надеюсь, без помощи с Вашей стороны.)

[Iosif1]

феодора писал(а):

Кроме того, это не просто вычеркивание чисел на старте, это другой ряд чисел, с другими законами, которые позволяют делать подобные рассчеты.

С этим утверждением не могу не согласиться. Посмотрите, пожалуйста, "Методику определения делимости чисел" на этом же форуме. Аналогичными закономерностями характеризуется и числовой ряд, составленный из чисел, которые за вычетом единицы, или после ее прибавления, делятся на 4 без остатка. При этом между числами числового ряда, составленного Вами, и того, о котором я пишу, имеет место строгая корреляционная зависимость. Она то и позволила составить невероятностный алгоритм определения простых чисел. Правда, может быть, подобная корреляционная зависимость существует и между числами числовых рядов, составленных на этих же принципах, но с использованием других делителей. Iosif1

[феодора]

Iosif1 писал(а):

[ Правда, может быть, подобная корреляционная зависимость существует и между числами числовых рядов, составленных на этих же принципах, но с использованием других делителей. Iosif1

Да, существует для всех рядов, но для определения простоты оптимальной является 6-чная периодизация.