[백준/BOJ/알고리즘/파이썬(python)]#1978_소수 찾기[수학/에라토스테네스의 체]

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

1978번: 소수 찾기

에라토스테네스의 체:

에라토스테네스의 체는 소수를 찾는 방법으로 알고리즘은 다음과 같다.

출처: 위키백과

x의 배수를 모두 지우고(위의 사진처럼 컬러링) 마지막으로 살아남은 녀석들이 소수(prime number)다.

import sys
input = sys.stdin.readline
N = int(input())

num_list = []

num_list=map(int, input().split())

prime_cnt=0

for i in num_list:
    #에리토스테네스의 체
    flag = 0
    if i > 1:
        for j in range(2, i//2+1):    
            if (i%j == 0):
                flag += 1 #배수는 배열에서 제거 
        if flag == 0:
            prime_cnt+=1 #배수가 아님 
print(prime_cnt)