Третья задача из проекта Эйлера

Question

Решил попробовать свои силы и взялся за проект Эйлера. В ступор ввела третья задача, вот её условие:

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

Вот мой код:

import math

input_number = 600851475143
number = math.ceil(math.sqrt(input_number))

lst = []

for i in range(3, number):
    if input_number % i == 0:
        lst.append[i]

print(lst[-1])

Вопрос таков: мой код выводит число 486847, но на всех сайтах правильный ответ - 6857. Почему не подходит мой ответ, ведь изначальное число делится на него без остатка?

Answer 1

вот переделанный ваш код:

import math

input_number = 600851475143
number = math.ceil(math.sqrt(input_number))

primes = []

for i in range(2, number):
    if input_number % i == 0:
        is_prime = True
        for prime in primes:
            if i % prime == 0:
                is_prime = False
                break

        if is_prime is True:
            primes.append(i)

print(primes)

результат:

[71, 839, 1471, 6857]

Answer 2

import math

input_number = 600851475143
number = math.ceil(math.sqrt(input_number))

lst = []

for i in range(3, number):
    if input_number % i == 0 and all(i % j for j in lst):
        lst.append(i)

print(lst[-1])

n = 600851475143

arr = []
i = 2
while n != 1:
    if n % i == 0:
        n //= i
        arr.append(i)
    else:
        i += 1

print(arr[-1])

Answer 3

 def f(n):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                return False
        return True
    
    x = 600851475143
    d = set()
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            d.add(i)
            d.add(x//i)
    
    pr = [j for j in d if f(j)==True]
    print(max(pr))

Вот моё решение третьей задачи

Answer 4

Более простой вариант, если вам нужно.

x = 600851475143
d = 0

for i in range(2,x):
    if x % i == 0:
        d = i
        x = x / i
    if i > x:
        break
print(d)

БЛОГ НА HUSL

Третья задача из проекта Эйлера

Ответы (4 шт):