Сайт Алексея Муртазина (Star Cat) E-mail: starcat-rus@yandex.ru
Мои программы Новости сайта Мои идеи Мои стихи Форум Об авторе Мой ЖЖ
VB коды Статьи о VB6 API функции Самоучитель по VB.NET
Собрания сочинений Обмен ссылками Все работы с фото и видео
О моём деде Муртазине ГР Картинная галерея «Дыхание души»
Звёздный Кот

Список моих идей
Поиск простых чисел - Отсев чётных чисел
Задача
   Допустим нам известно простое число 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 г.


Инфо
Сайт создан: 20 июня 2015 г.
Рейтинг@Mail.ru
Главная страница