[Baekjoon] 1978. 소수 찾기

소수 찾기

문제 설명

---

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4
1 3 5 7

예제 출력 1

3

문제 풀이

---

문제 자체는 소수인지 판별하는 단순한 문제인데, 소수 판별 알고리즘은 어느 문제에나 적용될 수 있으니 이번에 확실히 숙지하자.

첫 번째로, 가장 직관적인 방법으로 숫자 n에 대해 2부터 root(n) 까지의 숫자 중 n이 나누어 떨어지는 수가 있으면 소수가 아니라고 할 수 있습니다.

n = int(input())
nums = list(map(int, input().split()))
ans = 0
for num in nums:
    for i in range(2, int(num**(1/2))+2):
        if num % i == 0: break
    else: ans += 1
print(ans)

하지만 위의 방법은 각 숫자에 대해 매번 for문을 돌기 때문에, 큰 숫자들이 주어지면 시간이 매우 오래 걸립니다.

따라서, 우리는 에라토스테네스의 체라는 소수 찾기 알고리즘을 사용하도록 합니다.

n = int(input())
nums = list(map(int, input().split()))
maxnum = max(nums)
# 에라토스테네스의 체
isPrime = [False, False] + [True]*(maxnum-1)
for i in range(2, int(maxnum**(1/2))+1):
    if isPrime[i]:
        for j in range(2*i, maxnum+1, i):
            isPrime[j] = False

print(sum([isPrime[num] for num in nums]))

에라토스테네스의 체는 가장 큰숫자 maxnum에 대해 2부터 root(maxnum)까지 for문을 돌며 각 숫자의 배수를 지워갑니다. for문을 끝까지 돈 후에도 그 값이 True이면 소수인 것입니다.

소수를 찾아야 할 상황이 온다면, 이 알고리즘을 사용하여 풀이하는 것이 효율적일 것입니다.