Форум программистов, компьютерный форум, киберфорум
Наши страницы
Баженов
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Алгоритм проверки простых чисел.

Запись от Баженов размещена 10.09.2019 в 23:46

Алгоритм проверки простых чисел.
Алгоритм основан на использовании функций
П=x*y и С=x+y.
IШаг 1. Вычисляем n=(N-1):2.
Шаг 2. Из условия 2 П меньше n получаем последовательность допустимых значений П.
Шаг 3. Из полученной последовательности исключаем простые числа, так как они соответствуют числам,
кратным 3.
Шаг 4. Из оставшихся чисел исключаем четные числа так как они соответствуют числам, кратным 5.
Шаг 5 (последний) Для оставшихся П путем их разложения на два сомножителя проверяем возможность
выполнения равенства n=2П+С.

На одном примере числа 41 покажу,как работает этот алгоритм проверки.
Число 41. n=20 П< 10: 9,8,7,6,5,4,3,2,1.
Исключаем простые числа и получаем последовательность 10,9,8,6,4,2.
Исключаем четные числа и остается одно число 9.
Разлагаем число 9 на сомножители и получаем 9=3*3 (разложение 1*9 исключаем,так как оно
соответствует числу,кратному 3..
Для оставшегося разложения 3*3 вычисляем С=3+3=6.
И теперь вычисляем n=2*П + С= 18+6= 24
Оно больше 20 и,следовательно, число 41 является простым числом.!
Размещено в Без категории
Просмотров 91 Комментарии 1
Всего комментариев 1
Комментарии
  1. Старый комментарий
    Существует много различных алгоритмом для проверки чисел на простоту.
    Вот ещё один. Записываем все простые числа в ряд.
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ...
    А число то 41 и впрямь простое!
    Запись от нтч размещена 11.09.2019 в 07:24 нтч вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru