백준 알고리즘: 1978번 소수 찾기

문제 정보

---

1978번: 소수 찾기

 

 

핵심

---

소수를 구하는 방법을 알면 된다

정수 N을 2부터 N-1까지 나누었을 때 나누어지는 수가 없다면 소수라고 할 수 있다

이 문제의 경우 주어지는 수가 1,000 이하로 정해져 있고, 수가 비교적 작기 때문에 직접 주어지는 N을 2 ~ N-1 으로 하나하나 나누어서 소수인지 아닌지를 판별하면 되지만

수가 커지는 경우는 에라토스테네스의 체 알고리즘을 사용하여 풀이해야 한다

 

나는 에라토스테네스의 체 알고리즘을 사용하여 풀이하였다

에라토스테네스의 체에 관한 내용은 아래 참고에 링크를 달아두었으니, 모른다면 확인하면 좋을것 같다

 

풀이

---

from sys import stdin
import math
_ = stdin.readline()
N = list(map(int, stdin.readline().split()))

array = [True for _ in range(1001)]
array[0], array[1] = False, False
for i in range(2, int(math.sqrt(1000)) + 1):
    if array[i]:
        j = 2
        while i * j <= 1000:
            array[i*j] = False
            j += 1

count = 0
for n in N:
    if array[n]:
        count += 1
print(count)

먼저 에라토스테네스의 체 알고리즘을 사용하여 1,000까지의 수들이 소수인지 아닌지를 알 수 있는 배열을 만들었고

True라면 소수이고, False면 소수가 아니다

 

for문에서 2부터 1,000이 아닌 1,000의 제곱근인 math.sqrt(1000) 까지인 이유는

특정 수의 약수를 보면, 짝이 존재하는 것을 알고있을텐데

#16의 약수
1 2 4 8 16

우선, 16의 제곱근은 4이고 4를 기준으로 왼쪽과 오른쪽이 짝을 이룬다

2와 8을 보면, 4를 기준으로 2는 4보다 작고 8은 16보다 크다

16은 2로 나누어도 나누어지고, 당연히 그의 짝인 8로 나누어도 나누어진다

 

특정한 수 N이 있다고 할 때, N의 약수 중 한 쌍이 a, b라고 해보자

a와 b가 같은 수라면 a,b는 N의 제곱근이고 a=b일 것이다

a와 b가 다른 수라면 a * b = N 일 때 a, b 둘중 하나는 N의 제곱근보다 작은 수를 가질 것이다

 

따라서 우리가 위 알고리즘으로 계산할 때, N의 제곱근까지의 수만으로 소수를 판별하는데

a<b 인 경우, N의 제곱근보다 a가 작은 수이기 때문에 이미 판별이 완료된 수이기 때문에 b는 판별하지 않아도 짝을 이루는 a의 계산의 결과만으로 판단할 수 있는 것이다

 

 

참고

---

GitHub - dduneon/CodingTestPy

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전