[4주차] 소수판별 (에라토스테네스의 채)

https://www.acmicpc.net/problem/9020

https://wikidocs.net/21638

9020번: 골드바흐의 추측

 

골드바흐 추측에서 '에라토스테네스의 채'를 이용해서, 소수판별을 하자.

import sys
import math

n = int(sys.stdin.readline())
arr = list(int(sys.stdin.readline()) for _ in range(n))

box = [1] * 10001
box[0] = 0
box[1] = 0

for i in range(2, 101):
    j = 2
    if(box[i] == 1):
        while(i * j < 10001):
            box[i * j] = 0      
            j = j + 1