Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 31   вперед  Ctrl
 Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
В вики есть статья про решето Эратосфена – алгоритм нахождения всех простых чисел до некоторого целого р :
https://ru.wikipedia.org/wiki/Решето_Эратосфена
Там же описан псевдокод поиска простых чисел:

Вход: натуральное число n
Пусть A — булевый массив, индексируемый числами от 2 до n,
изначально заполненный значениями true.
для i := 2, 3, 4, ..., пока i2 ≤ n:
если A[i] = true:
для j := i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
A[j] := false
Выход: числа i, для которых A[i] = true.

Есть упрощения алгоритма:
- поиск идет только по нечетным числам;
- поиск идет начиная с квадрата числа.

В комментариях к сообщению
https://habr.com/ru/post/124605/
нашел следующее упрощение:

«Также обычно рассматривают числа виде 6k, 6k+1, 6k+2,6k+3,6k+4,6k+5. Здесь 6=2*3 произведению первых двух простых чисел. Из них 6k, 6k+2,6k+3,6k+4 делятся на 2 или 3.
Поэтому надо проверять на простоту только числа вида 6k+1, 6k+5 (33.3% от всех).
Это можно обобщить: например, рассматривая числа вида 30k, 30k+1,…
Но это становится громоздким при программирование и дает малый выигрыш
30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19,30k+23, 30k+29 (26.6% от всех)»

Может быть, я что-то пропустил. Битовые варианты специально не рассматривал.

Пятничная задачка в следующем:
как ещё можно упростить (или усложнить!) как алгоритм, так и массив для алгоритма таким образом, чтобы за определенный период времени можно будет найти большее количество простых чисел.
15 фев 19, 12:47    [21810476]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Gennadiy Usov
как ещё можно упростить (или усложнить!) как алгоритм, так и массив для алгоритма таким образом, чтобы за определенный период времени можно будет найти большее количество простых чисел.

Взять готовый список простых чисел. Он точно имеет наибольшее число сильно дальше, чем, чем размер булевого массива в памяти обычного писюка. Да и необычного, скорее всего, тоже. А промежутки в простых числах начинаются где-то очень-очень далеко по меркам, например, 64-битных чисел.

Перебор здесь как бы давно сделан. Поэтому нужно сам принцип поиска менять.
15 фев 19, 14:45    [21810717]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Перебор здесь как бы давно сделан. Поэтому нужно сам принцип поиска менять.
И я за то.

В одном из сообщений, как было сказано в первом сообщении данного топика:
автор
Это можно обобщить: например, рассматривая числа вида 30k, 30k+1,…
Но это становится громоздким при программирование и дает малый выигрыш
30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23, 30k+29 (26.6% от всех)»
Здесь известны 8 реперных точек.

Если взять от 210k до 210k +209, то будет 46 реперных точек, и будет 22,7% от всех.

То есть, при определении простых чисел рассматриваются только 22,75 от всех чисел р.

Пока не вижу громоздкость.
15 фев 19, 15:16    [21810777]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
В предыдущем сообщении ошибся - 43 реперные точки. И искать простые числа будем только среди 20,5% всех чисел.

Можно идти дальше.

Получаем 341 реперную точку для последовательности от 2310k+1 до 2310k+2309.
Применение этой последовательности позволит рассматривать только 15% всех чисел для нахождения всех простых чисел.
15 фев 19, 17:09    [21811018]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Тут обсуждали эту тему https://www.sql.ru/forum/1149455/generator-prostyh-chisel-do-10-9-za-5-sek
15 фев 19, 18:51    [21811115]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
В настоящее время программ по определению простых чисел - полно.
Наверное, многие когда-то попробовали определить некоторое количество таких чисел.
Все эти программы упираются в одно: за определённое время можно провести проверку чисел только до некоторого числа.
А хочется увеличить количество определяемых чисел.

Поэтому, наверное, интересно найти новые приёмы по увеличению количества определяемых простых чисел за конкретное время.

Работа с блоками Ak+B позволяет уменьшить количество чисел (в процентном отношении), среди которых можно вести поиск простых чисел.
15 фев 19, 19:08    [21811131]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56548
Gennadiy Usov
А хочется увеличить количество определяемых чисел.
Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое.
15 фев 19, 19:34    [21811151]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Aklin
Gennadiy Usov
А хочется увеличить количество определяемых чисел.
Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое.
можно проверить, что на 100% непростое
называется Малая теорема Ферма
15 фев 19, 19:49    [21811157]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
вру

тынц
15 фев 19, 19:50    [21811160]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Проблема в том что сложность алгоритма не уменьшается. Начни перебирать вместо подряд каждого - каждое сотое потенциально простое число, получишь ускорение в сто раз, т.е. всего на два порядка, а надо как минимум на 50 порядков ускориться.
15 фев 19, 19:55    [21811169]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Aklin
Gennadiy Usov
А хочется увеличить количество определяемых чисел.
Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое.
Хорошо. А сколько будет поверок?
Это хорошо для очень большого числа, а что будет с рядом стоящими?

Вот здесь как раз поможет "рамка" в виде блока Ak+B, которой "накрываем" область чисел над первоначальным числом.
И сразу будет видно, какие числа, которые находятся рядом с первоначальным числом, не надо будет рассматривать.
15 фев 19, 20:09    [21811193]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Dima T
Проблема в том что сложность алгоритма не уменьшается. Начни перебирать вместо подряд каждого - каждое сотое потенциально простое число, получишь ускорение в сто раз, т.е. всего на два порядка, а надо как минимум на 50 порядков ускориться.
А кто сказал, что можно посчитать все числа до ... даже представить сложно?

Уменьшили время расчетов в сто раз, значит в сто раз больше определили чисел. Уже хорошо.
Будем ещё что-то искать.

А почему Вы решили, что надо на 50 порядков? Может быть на 1000 порядков? Или на 10 порядков?
Что там говорит криптография?
15 фев 19, 20:15    [21811203]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
Aklin
пропущено...
Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое.
можно проверить, что на 100% непростое
называется Малая теорема Ферма
А почему не применяют тест Ферма, когда надо определить много простых чисел.

Здесь говорится, что определили, что число - непростое, но не сказано, что число - простое.
15 фев 19, 20:29    [21811219]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Откуда взято число 100?
15 фев 19, 20:51    [21811227]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Gennadiy Usov
Что там говорит криптография?
А что криптография, зачем там список всех простых? Для RSA нужно ровно два простых числа, причем очень больших и не сильно близких.
15 фев 19, 21:33    [21811247]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Barlone
Gennadiy Usov
Что там говорит криптография?
А что криптография, зачем там список всех простых? Для RSA нужно ровно два простых числа, причем очень больших и не сильно близких.
Уже нашли эти числа?
Или нужны числа на каждый день?
16 фев 19, 06:27    [21811378]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Откуда взято число 100?
Вопрос к какому сообщению? И если не 100, то что?
16 фев 19, 06:29    [21811379]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Gennadiy Usov
Barlone
пропущено...
А что криптография, зачем там список всех простых? Для RSA нужно ровно два простых числа, причем очень больших и не сильно близких.
Уже нашли эти числа?
Или нужны числа на каждый день?
На каждый секретный ключ
16 фев 19, 06:38    [21811380]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Gennadiy Usov
Работа с блоками Ak+B позволяет уменьшить количество чисел (в процентном отношении), среди которых можно вести поиск простых чисел.
Можно далее строить блоки:
30030k+B,
510510k+B,
9699690k+B,
…..,
304250263527210k+B
и т.д.

При увеличении размера блока можно довести количество проверяемых чисел от всех чисел в последнем варианте до 3%.

Дальнейшее увеличение величины блока позволит дальше уменьшать процент количества проверяемых чисел в зависимости от всех чисел.
16 фев 19, 09:02    [21811396]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Barlone
Gennadiy Usov
Уже нашли эти числа?
Или нужны числа на каждый день?
На каждый секретный ключ
Где можно найти алгоритм поиска секретных ключей (не программа)?
16 фев 19, 09:29    [21811401]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Это случайные числа.
16 фев 19, 10:24    [21811420]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Это случайные числа.
Нашли случайное, а оно не простое,
Где гарантия, что оно простое?
16 фев 19, 10:52    [21811426]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Gennadiy Usov
mayton
Это случайные числа.
Нашли случайное, а оно не простое,
Где гарантия, что оно простое?
https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
16 фев 19, 11:42    [21811453]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Barlone
Gennadiy Usov
Нашли случайное, а оно не простое,
Где гарантия, что оно простое?
https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
А в этой статье написано:

"Однако, с его помощью нельзя строго доказать простоту числа".
16 фев 19, 11:55    [21811471]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Gennadiy Usov
Barlone
пропущено...
https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
А в этой статье написано:

"Однако, с его помощью нельзя строго доказать простоту числа".

Для криптографии приемлемо доказать простоту с вероятностью. Кроме того Миллер-Рабин можно
усилить итерациями. Чем больше итераций тем больше вероятность простоты числа
приближается к 1 единице.

Это возможно и ответ на мой вопрос касательно теста https://habr.com/ru/post/205318/
16 фев 19, 12:53    [21811498]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 31   вперед  Ctrl
Все форумы / Программирование Ответить