結果
問題 |
No.3296 81-like number
|
ユーザー |
![]() |
提出日時 | 2025-10-05 13:40:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,016 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 65,116 KB |
最終ジャッジ日時 | 2025-10-05 13:41:31 |
合計ジャッジ時間 | 1,917 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
# 1 以上 N 以下の整数が素数かどうかを返す def Eratosthenes(N): # テーブル isprime = [True] * (N+1) # 0, 1 は予めふるい落としておく isprime[0], isprime[1] = False, False # ふるい for p in range(2, N+1): # すでに合成数であるものはスキップする if not isprime[p]: continue # p 以外の p の倍数から素数ラベルを剥奪 q = p * 2 while q <= N: isprime[q] = False q += p # 1 以上 N 以下の整数が素数かどうか return isprime isprime = Eratosthenes(10**5+10) N = int(input()) ans = 0 seen = set() for i in range(2, min(N,10**5)+1): if i in seen: continue if not isprime[i]: continue for j in range(2,35): val = i**j if val in seen: continue if val<=N: ans += val seen.add(val) else: break #print(sorted(list(seen))) print(ans)