ALDS_1_C: Prime Numbers (続き)

さてじゃあどうしよう
奇数偶数だけで分けるんじゃなくて、６で割った余りで分類することにすると
3000万回ループが節約できるな
でもあんまりスマートな気はしない

やっぱり１億までのふるいってのが無理あるのでは
１億までの数の素数の判定だから、１万までの素数をふるいで求めて
順番に割るっていう作戦もあるか
これならふるいにかかる時間は無視できる
１万までの素数がいくつあるかわからないけど1000として
ひとつの数の判定をするのに最大1000回の割り算
たいていはもっと速く終わるだろうから100回くらいになるとすると
1万個判定しても100万回の割り算
それくらいならいけるでしょう

sieveは昨日のをそのまま使ってこんな感じ

def primes(max):
    s = sieve(max)
    p = [2]
    for i in range(1, len(s)):
        if s[i] == 0:
            p.append(i * 2 + 1)
    return p


def is_prime(n, p):
    m = sqrt(n)
    for q in p:
        if q > m:
            return True
        if n % q == 0:
            return False
    return True

def main():
    p = primes(10000)
    n = int(input())
    sum = 0
    for _ in range(n):
        x = int(input())
        if is_prime(x, p):
            sum += 1
    print(sum)

00.12s 5704KBでAC
よかったよかった

解説
sqrt(n)までで割ればn - 1まで割るよりずっと早い
あらかじめ素数を用意した方がいいことがあってふるいが有効
知ってた

サンプルコード

・・・

ふるってねえ
そのままsqrt(n)まで割ってる

def is_prime(n):
    m = int(sqrt(n))
    for q in range(2, m + 1):
        if n % q == 0:
            return False
    return True

00.36s 5680KBでAC、って
ふるいの絵はなんだったのか
まあ３倍速いしな！

エラトステネスのふるいの計算量はO(N log log N)なんだって
へー へー へー