BOJ(백준) 1978[소수 찾기]

안녕하세요! 오늘은 백준 1978번 문제 “소수 찾기”를 풀어보겠습니다. 이 문제는 주어진 수들 중 소수가 몇 개인지를 찾는 문제입니다. 소수를 판단하는 알고리즘을 구현해보고, 이를 통해 소수의 개수를 세어보겠습니다.

 

1. 문제설명

 

문제 링크

문제 링크는 여기에서 확인하실 수 있습니다.

 

문제 내용

자연수 N이 주어졌을 때, N개의 수 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하세요.

 

입력

• 첫 줄에 수의 개수 N (1 ≤ N ≤ 100)

• 다음 줄에 N개의 수가 주어집니다. (각 수는 1보다 크거나 같고, 1000보다 작거나 같은 자연수)

 

출력

• 주어진 N개의 수 중에서 소수의 개수를 출력합니다.

 

2. 접근법

문제를 해결하기 위해 다음과 같은 접근 방법을 사용했습니다:

 

1. 소수의 정의: 소수는 1과 자기 자신 이외의 수로 나누어 떨어지지 않는 수를 의미합니다.

2. 소수 판단 함수: 주어진 수가 소수인지 여부를 판단하는 함수를 작성합니다.

3. 입력 처리: 표준 입력을 통해 수의 개수와 각 수를 입력받습니다.

4. 소수 개수 계산: 입력받은 수 중에서 소수의 개수를 세어 출력합니다.

 

3. Python 코드

import sys
input = sys.stdin.readline

# 소수여부 판단하는 함수
def chkPrime(num):
    if num == 1:
        return 1
    if num == 2 or num == 3:
        return 0
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return 1
    return 0

# 수의 개수 입력 처리
N = int(input())
arr = list(map(int, input().split()))

# 소수의 개수를 출력
ans = N

for i in arr:
    ans -= chkPrime(i)

print(ans)

 

4. 코드 설명

 

- chkPrime 함수:

• 입력된 숫자가 소수인지 아닌지를 판단합니다.

• 1은 소수가 아니므로 1을 반환합니다.

• 2와 3은 소수이므로 0을 반환합니다.

• 그 외의 수는 2부터 해당 수의 제곱근까지의 수로 나누어 떨어지는지 확인하여 소수가 아니면 1을 반환하고, 소수이면 0을 반환합니다.

 

- 메인 함수:

• 먼저 수의 개수를 입력받고, 각 수를 리스트 형태로 입력받습니다.

• 각 수가 소수인지 판단하여 소수의 개수를 세어 출력합니다.

 

*** 제곱근 까지만 검사하는 이유는? ***

 

1. 약수 쌍의 대칭성:

• 어떤 수 N이 있을 때, a * b = N을 만족하는 약수 쌍 (a, b)가 존재합니다. 예를 들어, 36의 경우 약수 쌍은 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)입니다.

• 여기서 주목할 점은 약수 쌍 (a, b)에서 a와 b 둘 중 하나는 항상 √N 이하라는 것입니다. 예를 들어, 36의 제곱근은 6이고, 36의 모든 약수 쌍 중에서 큰 쪽은 모두 6보다 작거나 같습니다.

 

2. 제곱근을 넘지 않는 약수:

• 만약 어떤 수 N이 소수가 아니라고 가정하면, N = a * b가 되는 a와 b가 존재할 것입니다. 여기서 a와 b 둘 다 √N보다 크다면, a * b는 N보다 커야 하므로 a나 b 중 하나는 반드시 √N 이하이어야 합니다.

• 따라서, N이 소수가 아니려면 2부터 √N까지의 어떤 수로 나누어 떨어져야 합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_02_01_1978.py at main · pcy4196/coTest