Проект Эйлера - Задача 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.

Я так решил.

8 комментариев:

  1. ода) казалось бы все так просто, но я бы фиг додумался

    ОтветитьУдалить
  2. Почему тогда с число 1421 не работает?

    ОтветитьУдалить
  3. неверно) есть делители больше

    ОтветитьУдалить
  4. там else надо добавить перед count += 1, иначе программа будет криво работать

    ОтветитьУдалить
  5. num = 600851475143
    div = []

    for i in range(1, num):
    if (num % i == 0):
    div.append(i)

    print(max(div))

    этот код пайтон думает очень долго 😂😂😂

    ОтветитьУдалить
  6. Этот комментарий был удален автором.

    ОтветитьУдалить
  7. Этот комментарий был удален автором.

    ОтветитьУдалить
  8. Код сверху работает только если данное число - произведение простых без повторных множителей...
    а я так сочинил, с удобствами )
    Md = 1; Nd = 0; d=[]
    x0 = x = int(input('введите натуральное число '))
    while x != 1:
    for i in range (2,x+1):
    if (x % i) == 0:
    Md = i; d += [i]; Nd += 1; x = int(x / i);
    break
    continue
    if (Nd == 1) or (x0 ==1):
    print('число ', x0, 'простое')
    else:
    print('Всего', Nd, 'делителей числа ', x0, ':', d, ' максимальный из них - ',Md)

    ОтветитьУдалить