kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS_1_C: Prime Numbers

整数論の章に入りました
最初は素数判定

ヒントは一目瞭然でエラトステネスのふるい

なんだけど

2 ≦ 与えられる整数 ≦ 10^8

1億までのふるい!?
メモリ制限65536KBってことは6500万バイトくらい
奇数だけ覚えることにすれば1バイトでひとつの数字を覚えておけば
ビットまで細かくしなくても足りることは足りるんだ

しかし1秒で終わるかね
Pythonだからもっと時間もらえるけど

ってPythonで普通に5000万要素の配列書いたらその場でメモリ不足になりそうだな
バイトってどう表現するんだ
bytearrayってのを使うっぽいな

まあエラトステネスのふるいくらいちょっと書いてみるか
TLEやMLEになってもそんなにもったいない気分を味わわずに済む

こんな感じかな

from math import sqrt

def sieve(max):
    s = bytearray(max // 2)
    k = sqrt(max)
    i = 3
    while i < k:
        for j in range(2 * i, max, i):
            if j % 2 == 1:
                s[(j - 1) // 2] = 1
        i += 2
        while s[(i - 1) // 2] == 1:
            i += 2
    return s

def is_prime(n, s):
    if n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        return True if s[(n - 1) // 2] == 0 else False

def main():
    s = sieve(100000000)
    n = int(input())
    sum = 0
    for _ in range(n):
        x = int(input())
        if is_prime(x, s):
            sum += 1
    print(sum)

main()

動かしてみるとさすがにしばらく待つけど1億までのふるいが作れてる
それだけでもすごいことだね
でもジャッジにかけるとCase #1で5.99sのTLE
メモリは54412KBなので足りているようだ