Что нового

Contest Проект Эйлера. Решение задачи № 3.

Человек Тьмы 0
19.04.2020
28
68
Третья задача проекта Эйлера на первый взгляд кажется простой и решается в три действия.
  1. Находим все делители заданного натурального числа.
  2. Среди всех делителей оставляем только простые делители.
  3. Среди простых делителей находим наибольший - это число и будет являться ответом на задачу.

Сразу в голове вырисовывается вложенный цикл, который объединяет два первых действия и находит простые делители любого введённого с клавиатуры числа (не только того, что задан в условии).
Реализация такого алгоритма на python3 ваыглядит следующим образом:
Код:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
print("{}\033[31m{}\033[0m{}". format("##" * 10,  " Задача 3 ", "##" * 10))
print("#  https://euler.jakumo.org/problems/view/3.html #")
print("##" * 25)
print(u"Каков самый большой делитель числа 600851475143, являющийся простым числом? ")
n = int(input(u"Введите число: "))
#Находим все делители данного числа
for x in range(1, n + 1):
    if n % x == 0:
        k = 0
        for y in range(1, x + 1):
            if x % y == 0:
                k += 1
        if k == 2:
            print(y, "- простой делитель.")
Этот код легко справляется с нахождением простых делителей числа 13195, которое указано в условии в качестве примера.

screen.png

Осталась самая малость: найти наибольшее число среди полученных простых делителей.

Но не тут - то было, я рано обрадовался.
Как только я попробовал ввести заданное в условии задачи число 600851475143, программа задумалась и на очень длительное время.
Процесс вычисления изложенным выше алгоритмом занимает внушительное время.

screen01.png


Для решения третьей задачи навыков программирования явно недостаточно.
Нужно включать знания математики и переписывать алгоритм.
Алгоритм должен максимально экономить ресурсы компьютера ))
 

Вложения

Последнее редактирование:
Верх Низ