Как вывести точные степени на Python?

Question

С помощью приведенного кода можно вывести все точные степени (не превосходящие данного числа), но только с конкретным показателем, введённым пользователем. А как вывести все точные степени вообще? Допустим, я хочу вывести все точные степени, не превосходящие числа 310610407. Как это сделать?

pow=int(input())
k=int(input())
i=1
while i**pow<=k:
    print(i**pow)
    i+=1

Answer 1

Можно так, наверное

import math

all_powers = []
number = int(input('Введите число: '))
for i in range(2, int(math.sqrt(number))+1):#второе число можно заменить на number, 
                                            #потому что все числа до number являются 
                                            #степенью себя же (n)^1 = n. Следовательно, все числа 
                                            #сами по себе будут включены в список итоговых
    for power in range(int(math.log(number, i))+1):
        new_power = i**power
        if new_power not in all_powers:
            all_powers.append(new_power)

print(all_powers)

Answer 2

Кажется работает:

k=int(input())
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
print(sorted(set(list)))

PS Внемлю конструктивной критике.

Answer 3

Простой перебор в Google Colab считается минут 6:

from tqdm.auto import tqdm

n = 310610407
powers = set()
for i in tqdm(range(2, n+1)):
    for j in range(2, n+1):
        x = i ** j
        if x > n:
            break
        else:
            powers.add(x)

print(len(powers))
print(sorted(list(powers)))

Вывод:

100% 310610406/310610406 [05:43<00:00, 897346.56it/s]
18334
[4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, ...

P.S. Ой, что-то при перезапуске у меня уже другое кол-во получилось, что-то Google Colab мудрит и оптимизирует странным образом. Надо ещё перепроверять...

Answer 4

Чисто теоретически, точными степенями, не превосходящими N, будут все числа от 1 до N. Т.к. любое число есть первая степень самого себя. )))

Но если практически, исключить 0 и 1, то все сведется к факторизации всех чисел от 1 до N.

Опишу только алгоритм, кодить лень. )

Нужно наколдовать по принципу решета Эратосфена.

создадим вектор из N чисел
получим все простые числа 1 до N и вычеркнем их из вектора
факторизируем все оставшиеся, получаем p1^q1 * p2^q2 * ... * pn^qn и оставляем только те, у которых q1=q2=...=qn > 1.
ВСЕ

Решение с вектором не сжирает много памяти. Факторизация позволит гибко выбирать по довольно изощренным условиям.

БЛОГ НА HUSL

Как вывести точные степени на Python?

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