помогите оптимизировать код для решения задачи егэ по информатика(25)

Question

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

символ ? означает ровно одну произвольную цифру; символ * означает любую последовательность цифр произвольной длины; в том числе * может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10⁷, найдите все числа, удовлетворяющие маске 34?8*9 имеющие более 4 простых делителей (не равных самому числу и 1). В ответ в порядке возрастания выпишите подходящие числа и их наибольшие простые делители.

мой код:

n = 0
def izi(n):
  d = 0
  dn = []
  for i in range(2, int(n/2) + 1):
    for j in range(2, (i//2) + 1):
      if i % j == 0:
        break
    if n % i == 0:
      d += 1
      dn.append(i)
  return dn
sp = []
for z in range(11):
  n = f'34{z}89'
  K = izi(int(n))
  if len(K) > 4:
    print(K)
  for x in range(11):
    n = f'34{z}8{x}9'
    K = izi(int(n))
    if len(K) > 4:
      print(K)
    for y in range(11):
      n = f'34{z}8{x}{y}9'
      K = izi(int(n))
      if len(K) > 4:
        print(K)

помогите увеличить скорость выполнения кода

Answer 1

Функция izi ошибается: izi(8) → [2, 4], izi(12) → [2, 3, 4, 6]. В списке простых собственных делителей есть не простые числа 4 и 6. Это потому что цикл по j не работает:

    for j in range(2, (i//2) + 1):
      if i % j == 0:
        break

Этот код буквально ничего не делает. Перебирает значения в цикле, выходит из цикла и ничего не делает. Можно предположить что вы хотели проверить что кандидат в делители i простой, то есть не делится ни на какой j, но не получилось.

Ваш код можно исправить так:

def izi(n):
    dn = []
    for i in range(2, n // 2 + 1):
        for j in range(2, i // 2 + 1):
            if i % j == 0:
                break
        else:
            if n % i == 0:
                dn.append(i)
    return dn

Во внутреннем цикле появился блок else:. Для цикла он запускается, если в цикле не вызывался break. А если break не вызывался, то i ни на что не делится, значит оно простое.

Работает. Теперь можно оптимизировать. Условие if n % i == 0: поднимем наверх цикла. Зачем проверять простоту числа, которое не делитель n?

def izi(n):
    dn = []
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            for j in range(2, i // 2 + 1):
                if i % j == 0:
                    break
            else:
                dn.append(i)
    return dn

В таком виде программа начинает выдавать результаты. Пока я это пишу получились такие ответы:

[3, 7, 37, 41, 107]
[3, 7, 17, 61, 157]
[3, 11, 13, 61, 131]
[3, 17, 23, 37, 79]
[3, 11, 13, 229, 349]
[7, 13, 23, 31, 53]
[3, 7, 17, 41, 79]
...

Печатается не то что нужно, но хоть что-то. Избавиться от проверки простоты i можно если n делить на найденный делитель, чтобы исключить его появление в будущем в составе других делителей. Цикл for изменился на while потому что верхняя граница цикла теперь меняется. В конце в список делителей добавляется n, который к этому моменту сам стал простым делителем:

def izi(n):
    dn = []
    i = 2
    while i <= n // 2:
        if n % i == 0:
            # очистка n от простого множителя i
            while n % i == 0:
                n //= i
            dn.append(i)
        i += 1
    if n > 1:
        dn.append(n)
    return dn

Перебирать i достаточно до корня квадратного из n:

def izi(n):
    dn = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            # очистка n от простого множителя i
            while n % i == 0:
                n //= i
            dn.append(i)
        i += 1
    if n > 1:
        dn.append(i)
    return dn

Теперь работает очень быстро. Дальше я оптимизировать не буду. Поправьте печать сами.

БЛОГ НА HUSL

помогите оптимизировать код для решения задачи егэ по информатика(25)

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