One Digit Factorization

解説

$1$ 桁の素数 $2, 3, 5, 7$ と非負整数 $a, b, c, d$ を用いて $N = 2^a \cdot 3^b \cdot 5^c \cdot 7^d$ と表せるか判定すれば良いです。

よって、以下のアルゴリズムが正当です。

• $p = 2, 3, 5, 7$ の順に以下を繰り返す。
  • $N$ が $p$ で割り切れるあいだ、 $N \leftarrow N \div p$ に更新することを繰り返す。
• 最終的に $N = 1$ となれば Yes と、そうでなければ No と答える。

各ケースごとに高々 $O(\log N)$ 回の割り算で済むので、この解法は十分高速です。

実装例 (Python3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def solve(N):
    for p in (2, 3, 5, 7):
        while N % p == 0:
            N //= p

    if N == 1:
        print("Yes")
    else:
        print("No")

T = int(input())
for _ in range(T):
    N = int(input())
    solve(N)