Почему мой алгоритм медленный?

Question

import math
def f(n):
  l = {}
  lst = [str(num) for num in range(1, n, 2) if all(num % i != 0 for i in range(2,int(math.sqrt(num))+1))]
    for i in lst[::-1]:
      even = 0
      for j in i:
        if int(j) % 2 == 0:
          even += 1
        l[i] = even
    return int(max(l, key=l.get))

Этот код должен выводить простое число с наибольшим количество четных цифр, но я не укладываюсь в рамки 12000мс для 1000 <= n <= 5000000. Что я сделал не так?

Answer 1

Если трошки подумать, а не сразу в лоб перебирать, то это число на первой же итерации находится.

Начинаем с конца и с числа, содержащего как можно больше четных цифр.

Кончаться должно на нечетное: [13579]
Начинаться с четного: [24]
В середине пока только четные: [02468] - 5 штук

Т.е первым шагом получаем проверку чисел от 4888889 до 2000001, где первая цифра - 2,4; последняя - любая нечетная; в центре 5 четных в любых комбинациях.

Если не найдется простого, следующим шагом проверяем такую комбинацию:

Кончаться должно на нечетное: [13579]
Начинаться с четного: [2468]
В середине пока только четные: [02468] - 4 штуки

Следующий шаг:

Кончаться должно на нечетное: [13579]
Начинаться с четного: [2468]
В середине пока только четные: [02468] - 3 штуки

Следующий шаг:

Кончаться должно на нечетное: [13579]
Начинаться с четного: [2468]
В середине пока только четные: [02468] - 2 штуки

Если не найдется, по второму кругу, добавляя одну нечетную в первые n-1 цифр.

Следующий шаг:

Кончаться должно на нечетное: [13579]
Начинаться с: [1-9]
В середине [0-9] - 5 штук п.п. 2 и 3 - из 6-ти чисел одно нечетное, остальные четные

и т.д.

Расписать код можно как угодно, нужно только перед проверкой чисел от 4888889 до 2000001 проверить границы диапазона. И вуаля:

БЛОГ НА HUSL

Почему мой алгоритм медленный?

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