[Python]백준 BaekJoon.AC 1978 : 소수 찾기(에라토스테네스의 체)

 

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

1978번: 소수 찾기

 

 

보통의 방법으로 풀 수 없음은 짐작했지만 에라토스테네스의 체를 이용해 풀어야 함은 떠올리지 못했다.

알고리즘 분류를 보고 직접적인 힌트를 얻었고, 조금의 복습이 필요했다.

 

알고자하는 수보다 작거나 같은 수를 대상으로 진행하면 된다.

1보다 큰 자연수의 배수를 지우는 방식이다. 이때, 만약 n의 배수라면 n을 제외한 모든 배수를 지우는 것이다.

설명이나 코드로 이해하기 난해할 수 있다.

그림으로 이해하는 편이 훨씬 쉽다.

 

 

https://blog.kakaocdn.net/dna/k46OV/btq2Nx3GU7j/AAAAAAAAAAAAAAAAAAAAAL3ptEJDB5_-TTQPOul4FHtopR8uZs4_MD44KWNNMGYD/img.gif?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1756652399&allow_ip=&allow_referer=&signature=uuX304qfcAOByQ%2FYIDhkocfjMRc%3D

 

 

내 방식이 더 복잡한지 아닌지는 모르겠으나..(복잡할듯하다)

더 직관적이며 순차적으로 해결하는 데에 초점을 맞췄다.

 

알고자 하는 수를 리스트로 받고, 그 중 가장 큰 수를 알아낸다.

이 수의 +1만큼 boolean list를 만들어준다.

우선 모두 True 취급해주고, 2의 배수부터 해당되는 수는 False로 변환해주는 방식이다.

가장 큰 수(large변수)보다 큰 배수는 다룰 가치가 없으므로 break.

 

최종적으로 남은 True는 소수가 된다.

이때, 1은 소수가 될 수 없음으로 1을 제외해주는 걸 잊지 말아야 한다.

 

+)파이썬은 내게 어렵다..ㅜ

 

 

 

import sys

N = int(input())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

last = nums[N-1]
task = [True] * (last+1)

for i in range(2, last):
    j = 2
    while True:
        temp = i * j
        if temp > last:
            break
        if task[temp] == True:
            task[temp] = False
        j = j + 1

count = 0
for n in nums:
    if task[n] == True:
        if n == 1:
            continue
        else:
            count = count + 1

print(count)