소수(Prime Number)는 1과 자기 자신을 제외한 어떤 수로도 나누어떨어지지 않는 수를 의미합니다. 소수를 판별하는 방법 중 대표적인 방법이 에라토스테네스의 체(Sieve of Eratosthenes) 입니다.

1. 소수 판별법: 에라토스테네스의 체

1.1 개념

에라토스테네스의 체는 특정 범위 내에서 소수를 빠르고 효율적으로 찾을 수 있는 알고리즘입니다. 이 알고리즘은 소수 판별을 단순한 나눗셈 연산보다 빠르게 수행할 수 있어 많은 경우에 사용됩니다.

에라토스테네스의 체 3단계

1. 소수의 범위만큼 1차원 배열을 생성
2. 2부터 시작하여 현재 숫자가 지워지지 않았을 경우, 해당 숫자의 배수를 모두 제거 (자기 자신 제외)
3. 배열의 끝까지 2단계를 반복한 후 남아있는 모든 수를 출력

이제 이를 실제 코드와 함께 살펴보겠습니다.

2. 백준 1978번 - 소수 찾기

2.1 문제 설명

N개의 숫자가 주어졌을 때, 그 중 소수인 숫자의 개수를 찾는 문제입니다.

입력

• 첫 번째 줄: 숫자의 개수 N (1 ≤ N ≤ 100)
• 두 번째 줄: N개의 정수 (1 ≤ Ai ≤ 1000)

출력

• 주어진 숫자 중 소수의 개수를 출력합니다.

2.2 코드 구현 (파이썬)

import sys

# 1단계: 소수를 판별할 범위만큼 리스트를 생성
arr = list(range(2, 1001))

# 2단계: 에라토스테네스의 체 적용
for i in arr[:]:  # `arr[:]`을 사용하여 원본 리스트를 복사
    arr = [j for j in arr if j % i != 0 or j == i]  # 배수를 제거하지만 자기 자신(i)은 남김

# 3단계: 입력값에 대해 소수 개수 판별
n = int(sys.stdin.readline().strip())
check = list(map(int, sys.stdin.readline().split()))

count = 0
for i in check:
    if i in arr:
        count += 1

print(count)

3. 코드 분석: 에라토스테네스의 체 적용

이 코드에서는 에라토스테네스의 체의 3단계를 다음과 같이 구현했습니다.

1단계: 소수의 범위만큼 1차원 배열 생성

arr = list(range(2, 1001))

• 2부터 1000까지의 정수를 리스트 arr에 저장합니다.
• 1은 소수가 아니므로 포함하지 않습니다.

2단계: 배수 제거 (에라토스테네스의 체 적용)

for i in arr[:]:  # 원본 리스트를 복사하여 순회
    arr = [j for j in arr if j % i != 0 or j == i]  # 배수 제거 (자기 자신 제외)

• 리스트를 순회하면서 i가 소수라면, i의 배수들을 제거합니다.
• 단, 자기 자신은 제거하지 않습니다.

3단계: 주어진 숫자에서 소수 개수 찾기

count = 0
for i in check:
    if i in arr:
        count += 1

• 주어진 입력값 리스트 check에서 소수인 숫자의 개수를 셉니다.
• 리스트 arr에 존재하는 값이라면 소수이므로 카운트를 증가시킵니다.

4. 실행 예제

입력 예시

4
1 3 5 7

출력 예시

3

과정

• 1은 소수가 아니므로 제외.
• 3, 5, 7은 소수이므로 총 3개가 출력됩니다.

5. 정리

에라토스테네스의 체를 활용하면 범위 내의 소수를 효율적으로 찾을 수 있습니다. 배열을 사용하여 배수를 제거하는 방식은 반복적인 나눗셈 연산을 줄이고 성능을 향상시키는 데 효과적입니다.