結果

問題 No.2379 Burnside's Theorem
コンテスト
ユーザー vjudge1
提出日時 2025-02-05 01:51:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 740 bytes
コンパイル時間 815 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 77,440 KB
最終ジャッジ日時 2025-02-05 01:51:17
合計ジャッジ時間 3,617 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def sieve(n):
    limit = int(math.sqrt(n)) + 1
    is_prime = [True] * (limit + 1)
    primes = []
    is_prime[0] = is_prime[1] = False
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return primes

def pfactors(n, primes):
    factors = []
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return len(set(factors))

def solve():
    n = int(input())
    primes = sieve(n)
    if pfactors(n, primes) <= 2:
        print("Yes")
    else:
        print("No")

solve()
0