How to check if X is a divisor of 60 to power of any integer?-CodePudding

I have a big and random number n and I need to check if this number is a divior of 60 to the power of ANY integer

For example:

Input:

9

Output:

True

because it is a divisor of 60^2

I have looked into factorization of numbers and divisiors to find a schematic but I was unsucessful

CodePudding user response：

Look at it this way:

60 = 2^2 * 3 * 5
60^2 = 2^4 * 3^2 * 5^2
60^3 = 2^6 * 3^3 * 5^3
...

So a positive integer n is a divisor of some power of 60 if and only if it can be written as

n = 2^k * 3^l * 5^m,

with k, l, and m being some integers >= 0.

In other words, the set of prime factors of n must be a subset of {2, 3, 5}.