検索BOJ 1978小数点

3651 ワード
2021.01.12 テキストリンク
acmicpc.net/problem/1978
時間1秒、メモリ128 MB
input :
  • 個数N(1<=N<=100)
  • N個(1<=個<=1000)
    • output :
  • 少数の出力.
    • 入力した数字は最大1000です.
    長さ1001のリストを並べ、小数に分けます.
    入力したN個の数字をインデックスのように見つけます.

    エラトステネスのふるい。


    小数を検索する方法.
  • 2から、素数を要求したい区間の全数をリストする.図中の灰色の矩形で囲まれた数はこれに相当する.
  • 2は少数なので、右に2と書きます./2の場合はすべて削除されます.
  • の残りの数のうち、3は少数なので、右に3と書きます./2の場合はすべて削除されます.
    • 残りの
  • では、5は少数なので、右に5と書きます./5の倍数をすべて削除します.
    • 残りの
  • では、7は少数なので、右側に7と書きます./7の倍数をすべて削除します.
  • ビット目のプロセス
    • を繰り返す.

    2つのwhile文を繰り返して書きました.
    import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

prime_num = [True] * 1001
prime_num[1] = False

i = 2
while i <= 1000:
    cnt = i + i
    while cnt <= 1000:
        prime_num[cnt] = False
        cnt += i
    i += 1

ret = 0
for item in data:
    if prime_num[item]:
        ret += 1
print(ret)
    AngularJS-Main-「スライダ動作原理myMouseOver」
    C#教科書を身につける.エージェント