結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:24:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,876 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 93,232 KB
最終ジャッジ日時 2025-06-12 16:24:43
合計ジャッジ時間 6,695 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in bases:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def is_prime_power(x):
    if x <= 1:
        return False
    if is_prime(x):
        return True
    for k in range(2, 61):
        p = round(x ** (1.0 / k))
        for delta in (-1, 0, 1):
            candidate = p + delta
            if candidate < 2:
                continue
            if candidate ** k == x:
                if is_prime(candidate):
                    return True
    return False

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    Q = int(data[0])
    test_cases = list(map(int, data[1:Q+1]))
    
    for N in test_cases:
        found = False
        
        # Check if N can be expressed as sum of two primes
        if N % 2 == 0:
            if N >= 4:
                for p in range(2, N // 2 + 1):
                    if is_prime(p) and is_prime(N - p):
                        found = True
                        break
        else:
            if (N - 2) >= 2 and is_prime(N - 2):
                found = True
        
        if found:
            print("Yes")
            continue
        
        # Check for a from 2 to 60
        for a in range(2, 61):
            max_p = int(N ** (1.0 / a))
            for p in range(2, max_p + 1):
                if is_prime(p):
                    x = p ** a
                    if x > N:
                        break
                    y = N - x
                    if y <= 0:
                        continue
                    if is_prime_power(y):
                        found = True
                        break
            if found:
                break
        if found:
            print("Yes")
            continue
        
        # Check for b from 2 to 60
        for b in range(2, 61):
            max_q = int(N ** (1.0 / b))
            for q in range(2, max_q + 1):
                if is_prime(q):
                    y = q ** b
                    if y > N:
                        break
                    x = N - y
                    if x <= 0:
                        continue
                    if is_prime_power(x):
                        found = True
                        break
            if found:
                break
        if found:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()
0