백준 1978번 파이썬 _ 소수찾기 (에라토스테네스의 체)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제유형 : 수학, 에라토스테네스의 체 

문제풀이 :

• 2부터 차례대로 담긴 배열을 순회하면서, 배수들을 전부 표시하고 표시된걸 만나면 건너뛰는식으로 소수가 아닌것들을 전부 표시한다
• 예를들어 2는 표시가 안되어있으므로 4,6,8,10 ... 로 표시를 하고 3도 마찬가지로 6,9,를 표시할건데 이미 앞에서 6이 표시되었으므로 이때는 건너띄고 9로 넘어간다.
• 만약 4처럼 처음부터 바로 2에의해 표시된 수를 만난경우 바로 건너뛴다. (다음으로_ 5로)

참고 : m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221233595886&referrerCode=0&searchKeyword=%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4

22. 에라토스테네스의 체

 

정답코드 :

import sys
input = sys.stdin.readline

n = int(input())
array = (list(map(int, input().split())))
end = max(array)

check = [i for i in range(end+1)] #숫자와 인덱스를 같게 해주기 위해서 배열길이 +1
check[1] = 0    # 0, 1번째 인덱스는 0으로 두고 2번째부터 인덱스 = 값(숫자) 일치시킬수있도록
count = 0


for i in check[2:]:
    if check[i] == 0: #첫시작부터 0이면 다음번으로 뛰기 (4와같이 2로인해 이미 표시된것들)
        continue
    else:
        for j in range(2, (end // i) + 1): # 자기자신은 뺴야하므로 배수를 만들기위해 곱하는 숫자는 2부터시작, 끝은 배수가 최대숫자를 넘기지 않아야 하므로 end//i로한다.
            if check[i * j] == 0: #만약 넘어가고 있는 배수가 이미 체크되었으면 건너띄고
                continue
            else:
                check[i * j] = 0 #그렇지 않다면 0으로 만들면서 체크한다.
count = 0
for i in array:
    if i in check:
        count +=1
        
''' check 배열최종 : [0, 0, 2, 3, 0, 5, 0, 7] '''

print(count)