2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 17:48 


31/08/06
20
Поиск простых чисел - Отсев чётных чисел
Задача
Допустим нам известно простое число 31. Необходимо найти следующее число.
Этап №1 – поиск простых делителей
Первое нечётное число: 3. Поэтому делим $31/3=10$ и отбираем простые числа от 3 до 10. Это 3, 5, 7.

Этап №2 – вычисление остатка
Делитель №1) $31/3=10$, остаток - 1
Делитель №2) $31/5=6$, остаток - 1
Делитель №3) $31/7=4$, остаток - 3

Этап №3 – отсев чётных чисел
Например, размер шага равен 10, то есть ищем от 32 до 41.
У делителя №1 - 3, остаток – 1, $3-1=2$. Зачёркиваем номера из 10ка начиная с двойки: 2, 5, 8, новый остаток – $10-8=2$. Оставшиеся чётные числа: 4, 6, 10.
У делителя №2 - 5, остаток - 1, $5-1=4$. Зачёркиваем номера из 10ка начиная с четвёрки: 4, 9, остаток – $10-9=1$. Оставшиеся чётные числа: 6, 10.
У делителя №3 - 7, остаток - 3, $7-3=4$. Зачёркиваем номера из 10ка начиная с четвёрки: 4, новый остаток – $10-4=6$. Оставшиеся чётные числа: 6, 10.

Проверка
Осталось два чётных числа: 6 и 10.
1) $31+6=37$. Поскольку число увеличилось, то количество простых делителей так же могло увеличиться. $37/3=12$. Ищем от 11 до 12. Это 11. Проверяем $37/11=3$, остаток – 4. Значит 37 - первое простое число!
2) $31+10=41$. $41/3=13$. 13 – простое число. Проверяем $41/13=3$, остаток – 2. 41 - второе простое число!
Найдено два простых числа: 37, 41.
ЗАДАЧА РЕШЕНА!

Итог
Чтобы продолжить поиск надо суммировать 31 и размер шага: $31+10=41$ – новая точка отсчёта. И повторить этап №3, добавив два новых делителя 11, 13.
Преимущество данного метода в том, что найденное простое число не нуждается в проверке поскольку, при его поиске использовались все возможные делители. К тому же легко перейти к поиску следующего числа.
4 января 2018 г.

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 18:10 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Star Cat в сообщении #1281237 писал(а):
Преимущество данного метода в том, что найденное простое число не нуждается в проверке поскольку, при его поиске использовались все возможные делители. К тому же легко перейти к поиску следующего числа.

У этого метода нет никаких преимуществ, это излишнее усложнение древнего метода решета Эратосфена, к тому же косноязычно и мутно записанное.

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 20:55 


31/12/10
1555
Star Cat
$198406007$ - простое число, найдите следующее простое число.

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 22:27 


31/08/06
20
vorvalm в сообщении #1281289 писал(а):
Star Cat
$198406007$ - простое число, найдите следующее простое число.

Какой смысл его искать?

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 22:47 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
А какой смысл в том, что Вы написали в стартовом сообщении? Вы ведь хотите предложить какой-то суперэффективный метод нахождения простых чисел. Зачем? Вас просят продемонстрировать его эффективность на совсем небольшом девятизначном числе.

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 22:58 


31/08/06
20
Someone в сообщении #1281325 писал(а):
А какой смысл в том, что Вы написали в стартовом сообщении? Вы ведь хотите предложить какой-то суперэффективный метод нахождения простых чисел. Зачем? Вас просят продемонстрировать его эффективность на совсем небольшом девятизначном числе.

Мне нужен список простых чисел до 66135335.

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение04.01.2018, 23:37 
Заслуженный участник


09/05/12
25179
Star Cat в сообщении #1281329 писал(а):
Мне нужен список простых чисел до 66135335.
Я сейчас так, интереса ради, написал простейшую реализацию решета Эратосфена. Написание кода заняло примерно 3 минуты, выполнение - около 2 секунд. Вы уверены, что на оптимизацию такой задачи (даже если оная будет успешной) стоит тратить более получаса? :wink:

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение05.01.2018, 00:59 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
А зачем такой большой? Для решета Эратосфена обычно достаточно иметь список простых, не превосходящих квадратного корня плюс ещё пара на всякий случай.

Star Cat в сообщении #1281237 писал(а):
Преимущество данного метода в том, что найденное простое число не нуждается в проверке поскольку, при его поиске использовались все возможные делители.
Числа, оставшиеся после применения решета Эратосфена, тоже гарантированно простые. При этом оно явно проще вашего метода.

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

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение13.01.2018, 20:15 
Аватара пользователя


29/01/15
559
Цитата:
...Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Пришла в голову идея записывать в файл не сами числа, а расстояния между ними. А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт...


База данных простых чисел

 Профиль  
                  
 
 Re: Поиск простых чисел - Отсев чётных чисел
Сообщение14.01.2018, 06:41 


20/03/14
12041
Degen1103
Проблема хранения простых чисел ТС не волновала.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group