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

Я так решил.

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

  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))

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

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

      for i in range(2, num):
      if (num % i == 0):
      div = num / i
      print(div)
      так же долго думает но ответ получим уже в первой строке

      Удалить
    2. в конце брейк тыкнут и вообще проблем не будет

      Удалить
  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)

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

    ОтветитьУдалить
  10. def prime_factors_func():
    prime_factors = []
    n = 600851475143
    for i in range (2, n-1, 1):
    if n % i == 0:
    prime_factors.extend([i])
    else:
    continue
    print(max(prime_factors))
    prime_factors_func()

    Единственное, что оооочень долго. Видимо, всё-таки не самая подходящая асимптотика. Но другие варианты в голов пока не приходя. Только перебором...

    ОтветитьУдалить
  11. Только начинаю учить питон, не все знаю, но пытаюсь решать задачи, пока кажутся очень сложными))
    Над этой задачей думал больше всего, с час, дошел до такого решения:

    n = 600851475143
    for i in range(2, n + 1):
    if n % i == 0:
    flag = True
    for i2 in range(2, i):
    if i % i2 == 0:
    flag = False
    if flag == True:
    print(i, end=' ')

    Не понял как заставить программу запомнить все числа и выбрать максимальное, она просто выводит все простые делители числа по возрастанию, и последнее из них является максимальным, что есть ответ

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

    ОтветитьУдалить
  13. Вашы варианты лаконичнее, но мой быстрее в 3 раза

    def IsSimpleNumber(n):
    for i in range(2, n):
    if n % i == 0:
    return False
    break
    else:
    return True
    def NextDiv(n):
    i = 2
    while i1:
    if IsSimpleNumber(i):
    print("Max simple divider: ",i)
    break
    i = NextDiv(i)

    ОтветитьУдалить
  14. только начал изучение питона, не судите строго, у меня получилось так:
    n = 600851475143
    i = 2
    mx = 1
    mn = 1
    for i in range(i, n):
    if n % i != 0:
    i += 1
    mn = i
    else:
    mx = n // mn
    print(mx)
    break

    ОтветитьУдалить
  15. a = 60085147
    i = a // 2
    while True:
    if a % i == 0:
    print(i)
    break
    i -= 1

    Только код выполняется , очень долго)

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

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

    ОтветитьУдалить
  18. l = []
    a = 600851475143
    for i in range(2, int(a**0.5)):
    if a % i == 0:
    l.append(i)
    if a // i not in l:
    l.append(a // i)
    print(max(l))

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

    ОтветитьУдалить
  20. a = 600851475143
    b = []
    c = 2
    while a != 1 or a > c:
    if a % c == 0:
    a /= c
    b.append(c)
    c += 1
    print (b[-1])

    Переменная а - для заданного числа
    Переменная с - для искомого делителя
    Пустой список b - для сохранения найденных делителей
    Создал цикл с условием крутить пока переменная а не будет ровна 1, или пока а не станет меньше с
    Далее в цикле условие: если а делится на с без остатка, то поделить и перезаписать результат в переменную а и в список b добавить значение делителя. По завершению цикла print последнего элемента в списке
    6857

    ОтветитьУдалить
  21. Опрошу оценить мое решение на Python. Начал изучать недавно, надеюсь мое решение является правильным. ответ 6857

    x = 600851475143
    for y in range(1, x):
    if x % y == 0:
    x = x / y
    elif x == 1:
    break
    print(y)

    ОтветитьУдалить
  22. a=600851475143
    b=0
    x=1
    z=0
    while a%(x+1)!=0:
    if a%x!=0:
    x=x+1
    elif x==1:
    x=x+1
    else:
    b=x
    else:
    b=x+1
    z=a/b
    print(z)



    Ребят вот самый верный код , работает для любого числа.
    Немного поясню:
    Если взять число,например, 4626 и поделить на 2, получится 2313- это число будет являться наибольшим , на которое делится 4626.
    Другой пример. Возьмем 735696, самое маленькое число , на которое делится 735696 будет 3( всегда исключаем 1) , получаем в итоге 245 232- это число является наибольшим, на которое мы можем разделить 735696.
    алгоритм в целом не сложный , попробуйте разобраться.
    Мне 16).

    ОтветитьУдалить
    Ответы
    1. a=600851475143
      b=0
      x=1
      z=0
      while a%(x+1)!=0:
      if a%x!=0:
      x=x+1
      elif x==1:
      x=x+1

      Одна строка была лишняя.

      else:
      b=x+1
      z=a/b
      print(z)

      Удалить