結果

問題 No.312 置換処理
ユーザー lam6er
提出日時 2025-04-15 21:16:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 552 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 58,996 KB
最終ジャッジ日時 2025-04-15 21:22:12
合計ジャッジ時間 3,059 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def find_smallest_prime_factor(d):
    if d % 2 == 0:
        return 2
    max_divisor = int(math.isqrt(d)) + 1
    for i in range(3, max_divisor, 2):
        if d % i == 0:
            return i
    return d  # d is prime

def main():
    N = int(input().strip())
    if N % 2 == 0:
        d = N
        while d % 2 == 0:
            d //= 2
        if d == 1:
            print(4)
        else:
            print(find_smallest_prime_factor(d))
    else:
        print(find_smallest_prime_factor(N))

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