Люблю такие задачки :), покритикуйте: #!/usr/bin/env python3 """ Задача: Простые делители числа 13195 -

Question

Люблю такие задачки :), покритикуйте: #!/usr/bin/env python3 """ Задача: Простые делители числа 13195 -

это 5, 7, 13 и 29.
Какой самый большой делитель числа 600851475143 являющийся простым числом?

Решение:
Возможно его и можно еще как - то еще оптимизировать,.
но я исходил из того что:
1. наибольший делитель всегда меньше половины числа,.
потому начинаем с середины и вниз.
(хотя тут я может и не прав и стоит всеже снизу искать)
2. простое число всегда нечетное, потому декремент делаем по 2 а не по 1
3. сначала ищем делитель, а потом проверяем его на простоту
"""
#x = 600851475143
x = 13195

n = x >> 1 # делим на 2
if not n % 2: # если оно четное,
n -= 1 # уменьшаем на 1

while n > 1: # уменьшаем до единицы
if x % n == 0: # если делится без остатка, то проверяем его на простоту
i = n >> 1 # тут тоже начинаем считать от середины
if not i % 2: # проверка на четность
i -= 1 # и уменьшаем при необходимости
while i > 1: # собственно цикл поиска
if n % i == 0: # если находим любой делитель
break # то выходим
i -= 2 # ищем только по нечетным
if i == 1: # если нашли простое
break # то останавливаем поиск
n -= 2

print("Наибольший простой делитель для числа {}: {}".format(x,n))

#backend #programming #python #russian

0

12.12.2019

1 ответов

12 просмотров

Буйный Виталя 🇮🇱 · Accepted Answer

Буйный Виталя 🇮🇱

Декремент слишком маленький

0

12.12.2019

170 похожих чатов

Люблю такие задачки :), покритикуйте: #!/usr/bin/env python3 """ Задача: Простые делители числа 13195 -

1 ответов

Похожие вопросы