Python Program To Check Powerful Number

A powerful number is a positive integer number such that every prime factor and their square divides a number.

Powerful number example: 72 is powerful number because prime factors of 72 are 2 & 3. First checking by 2: 72 is divisible by 2 and its square 4 i.e. 72/2 = 36 and 72/4 = 18. Similarly checking by 3: 72 is divisible by 3 and its square 9 i.e. 72/3 = 24 and 72/9 = 8.

First few powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 144, 169, 196, 200, 216, ...

This python program checks whether a given number by user is powerful number or not.

Python Source Code: Powerful Number

# Function definition to get all prime factors
def get_prime_factors(n):
    i = 2
    prime_factors = []
    while i*i <= n:
        if n%i == 0:
            prime_factors.append(i)
            n //= i
        else:
            i += 1
    
    if n>1:
        prime_factors.append(n)
    
    return prime_factors

def is_powerful(n):
    # get prime factors
    prime_factors = get_prime_factors(n)
    
    # filter to get unique prime factors
    unique_prime_factors = tuple(dict.fromkeys(prime_factors))
    for p in unique_prime_factors:
        if n % p != 0 or n % (p*p) != 0:
            return False
    return True

# Read number from user
number = int(input('Enter number: '))

# Function call & making decision
if is_powerful(number):
    print('%d is powerful' %(number))
else:
    print('%d is Not Powerful' %(number))

Powerful Check Output

Run 1:
-----------------
Enter number: 36
36 is powerful

Run 2:
-----------------
Enter number: 45
45 is Not Powerful