0

Всем привет. Написал код для задачи 3 проекта Эйлера. На небольших числах всё работает, в том числе и на 13195, которое даётся в примере, но на том, что в условии, Питон зависает на неопределённое время... Подскажите в чём проблема? Неужели настолько плохой код.. Или дело в чём-то другом? Код следующий:

#The prime factors of 13195 are 5, 7, 13 and 29.
#What is the largest prime factor of the number 600851475143?

number = 600851475143

all_factors = (i for i in range(2, (number//2+1)) if number%i == 0)
prime_factors = (x for x in all_factors if all(x%y !=0 for y in range(2, (x//2+1))))

print(max(prime_factors))
6
  • 4
    Проект Эйлер не рассчитан на тех, кто только начал изучать программирование. Советую вернуться к нему позже, когда начнете изучать теорию алгоритмов.
    – extrn
    16 авг 2021 в 1:32
  • 5
    @Chaose_in_June Попробуем прикинуть, сколько времени занимает выполнение Вашего алгоритма. Предположим, что выполение одной интерации цикла for x in all_factors занимает всего 1 мкс. Количество повторений цикла равняется (грубо говоря) половине от number. Тогда общее время вычислений = 600 851 cek / 2 = 83.5 часа = почти 4 суток.
    – Sergey
    16 авг 2021 в 1:53
  • 2
    Код неплохой. Алгоритм плохой. Смотри, нужно найти всего один множитель (самый большой),а ты зачем-то ищешь все, начиная с самого маленького. Или сразу самый большой (подсказка: range может работать на только от 2 до 1000, но и от 1000 до 2, да и шаг может быть любым). А по определению простоты числа тут примерно 100500 вопросов, посмотри там, как более оптимально это делать. 16 авг 2021 в 5:28
  • А если воспользоваться поиском, то подобные задачки тут уже решались 100500 раз, только надо их найти )
    – CrazyElf
    16 авг 2021 в 6:07
  • Про верхнюю границу я немного перепутал, поэтому удалил. 16 авг 2021 в 6:58

1 ответ 1

1

При рассчете простых чисел нет смысла бежать до половины числа. Есть смысл бежать до квадратного корня. Меняем

(number//2+1))

на

(int(math.sqrt(number))+1))

и все начинает очень быстро работать

5
  • math.sqrt быстрее **0.5 ?
    – Интик
    16 авг 2021 в 7:27
  • недавно было обсуждение на эту тему. Но думаю, в этом случае это абсолютно не важно. Но побенчмаркать всегда можно
    – KoVadim
    16 авг 2021 в 7:32
  • stackoverflow.com/questions/327002/… - но там все не так однозначно
    – KoVadim
    16 авг 2021 в 7:44
  • Только в этом случае нужно проверять на простоту как делитель, так и частное. 16 авг 2021 в 8:09
  • в прод коде - да. в рассчетных задачах на Эйлере - вряд ли
    – KoVadim
    16 авг 2021 в 8:10

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.