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なので足りているようだ