Точные степени, содержащие номер года

Question

Требуется написать программу, выводящую все точные степени, не превосходящие введённого пользователем числа, из десятичной записи каждой из которых можно вычеркнуть некоторые цифры так, чтобы остался номер введённого пользователем года. Например (как и случилось в вышеупомянутой задаче), пятая степень числа 17, равная 1419857, содержит в себе 1987 год (нужно вычеркнуть цифры 4, 1 и 5).

Приму любые замечания по коду:

def powers(k):

# Процедура выводит все точные степени, 
# не превосходящие введённого пользователем числа.

d=0
while 2**(d+1)<=k:
    d+=1
list=[]
for pow in range (2, d+1):
    i=1
    while i**pow<=k:
        list.append(i**pow)
        i+=1
return sorted(set(list))

# Теперь пишем программу, выводящую все точные
# степени, не превосходящие введённого пользователем
# числа, из десятичной записи каждой их которых можно  
# вычеркнуть некоторые цифры так, чтобы остался номер 
# введённого пользователем года. Например, пятая степень 
# числа 17, равная 1419857, содержит в себе 1987 
# год (нужно вычеркнуть цифры 4, 1 и 5). 

max=int(input()) 
year=input() # Год, который останется после вычёркивания.
A=powers(max) # Все точные степени, не превосходящие max.
for i in range(len(A)):
    num=str(A[i])
    i1 = 0
    i2 = 0
    while i1< len(num) and i2 < len(year):
        if num[i1] == year[i2]:
            i2 += 1
        i1 += 1
    if i2==len(year):
        print(num)

Answer 1

Функцию, дающие все степени меньше заданного числа можно написать гораздо проще:

def powers(maximum):
    if maximum < 1:
        return set()
    powers_set = {1}
    num = 2
    while num*num <= maximum:
        c_num = num
        for i in range(int(math.log(maximum, num)) - 1):
            c_num *= num
            powers_set.add(c_num)
        num += 1
    return  sorted(powers_set)

При большом максимальном числе у вас на машине закончится память => превращаем функцию в генератор:

def powers(maximum):
    if maximum < 1:
        return set()
    powers_set = {1}
    num = 2
    while num*num <= maximum:
        c_num = num
        for i in range(int(math.log(maximum, num)) - 1):
            c_num *= num
            yield c_num
        num += 1

Цикл проверки чисел на возможность "превращения" в год

numbers = []
for number in powers(maximum):
    try:
        indexes = [str(number).index(dec) for dec in year]
    except ValueError: # если не все цифры есть - следующее число
        continue
    else: # если все цифры "на месте" проверяем их порядок
        if indexes == sorted(indexes):
            numbers.append(number)
print(*sorted(numbers), sep='\n')

Ну и вся программа целиком:

import math

def powers(maximum):
    if maximum < 1:
        return set()
    powers_set = {1}
    num = 2
    while num*num <= maximum:
        c_num = num
        for i in range(int(math.log(maximum, num)) - 1):
            c_num *= num
            yield c_num
        num += 1

maximum = int(input())
year = input()
numbers = []
for number in powers(maximum):
    try:
        indexes = [str(number).index(dec) for dec in year]
    except ValueError: # если не все цифры есть - следующее число
        continue
    else: # если все цифры "на месте" проверяем их порядок
        if indexes == sorted(indexes):
            numbers.append(number)
print(*sorted(numbers), sep='\n')

Answer 2

Не занимайте имена глобальных функций и пакетов. У вас это list, pow, max.

Функция powers накапливает все числа в списке прежде чем сделать из него set. Это ненужный перерасход памяти. Циклы по показателю и основанию степени удобно поменять местами:

def powers(n):

    def gen():
        yield 1
        for b in range(2, 1 + math.isqrt(n)):
            p = b * b
            while p <= n:
                yield p
                p *= b

    return sorted(set(gen()))

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

def number_inside(n, seq):
    # '1.*9.*8.*7'
    r = re.compile('.*'.join(str(n)))
    return (m for m in seq if r.search(str(m)) is not None)

Уберем лишние функции, упростим код:

import math
import re


def powers_gen(n):
    yield 1
    for b in range(2, 1 + math.isqrt(n)):
        p = b * b
        while p <= n:
            yield p
            p *= b


n = int(input())
y = int(input())
r = re.compile('.*'.join(str(y)))
for m in sorted(set(powers_gen(n))):
    if r.search(str(m)) is not None:
        print(m)

БЛОГ НА HUSL

Точные степени, содержащие номер года

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