Проект Эйлера - Задача 3


Наибольший простой делитель

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

Моё решение (Python) под катом:
Для решения этой задачи я взял пример как разложить число на простые делители:


И исходя из этого примера и написал алгоритм по нахождению самого большого делителя.
num = 600851475143 count = 2 while 1: if num % count == 0: num /= count if num == 1: print(count) break count += 1

  • Возьмем заданной число и поделим его на два. Если делится без остатка - знат 2 простой делитель. Если не делится - знать делаем 2 + 1 и делим заданной число на 3.
  • После нахождения первого делителя, делим на него число из задачи и вписываем его на место оригинального числа.
  • Повторяем луп пока то число что мы проверяем не будет равно одному.
  • Выдаем это самое значение при котором проверочное число равно одному.

Мой ответ 6857.

Я так решил.

Комментариев нет:

Отправка комментария