Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Checking Perfect Power by freeman_lex
from math import gcd
from functools import reduce
def perfect_power(n: int) -> bool:
# Initialize lists to store prime numbers and their powers
primes, powers = [2], [0]
# Create an iterator for odd numbers starting from 3 up to n//2
it = range(3, n // 2 + 1, 2)
while ...:
# Get the last prime number in the list
curr = primes[-1]
# Divide n by the current prime while it's divisible
while not n % curr:
powers[-1] += 1
n //= curr
# If the power of the current prime is 1, n is not a perfect power
if powers[-1] == 1: return False
# If n has been fully factored and powers have been collected,
# check if the greatest common divisor of powers is greater than 1
if n == 1: return reduce(gcd, powers) > 1
# Find the next prime number using the iterator
nex = next(num for num in it if all(num % j for j in primes))
# Append the next prime to the list
primes.append(nex)
# If there was a non-zero power collected, append 0 to the powers list
if powers[-1]: powers.append(0)
print("Example:")
print(perfect_power(9))
# These "asserts" are used for self-checking
assert perfect_power(8) == True
assert perfect_power(42) == False
assert perfect_power(441) == True
assert perfect_power(469097433) == True
assert perfect_power(4922235242952026704037113243122008064) == True
print("The mission is done! Click 'Check Solution' to earn rewards!")
Aug. 22, 2023
Comments:
