結果

問題 No.3079 Unite Japanese Prefectures
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:28:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 628 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,120 KB
実行使用メモリ 64,980 KB
最終ジャッジ日時 2025-03-31 17:29:59
合計ジャッジ時間 2,550 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    max_n = 10**5
    sieve = [True] * (max_n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(max_n**0.5) + 1):
        if sieve[i]:
            sieve[i*i::i] = [False] * len(sieve[i*i::i])
    
    primes_count = [0] * (max_n + 1)
    cnt = 0
    for i in range(max_n + 1):
        if sieve[i]:
            cnt += 1
        primes_count[i] = cnt
    
    input = sys.stdin.read().split()
    T = int(input[0])
    for i in range(1, T+1):
        N = int(input[i])
        res = (N - 1) - primes_count[N]
        print(res if res >= 0 else 0)
        
if __name__ == "__main__":
    main()
0