Python) 백준 1978번 소수 찾기

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

 

백준 1978번 - 소수 찾기 문제 풀이

오늘은 백준 문제 중 하나인 1978번 - 소수 찾기 문제를 풀어보며 배운 내용을 기록하려 합니다. 이 문제는 주어진 수들 중에서 소수가 몇 개인지 찾아 출력하는 문제입니다. 간단한 소수 판별 문제이지만, 효율적인 풀이법도 고민할 수 있는 기회가 됩니다.

---

📌 문제 설명

주어진 N개의 수 중 소수가 몇 개인지를 출력하는 프로그램을 작성합니다. 소수는 1과 자기 자신 외에는 나누어떨어지지 않는 수를 의미합니다.

💡 입력

• 첫 번째 줄에는 자연수 N이 주어집니다. (N ≤ 100)
• 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어집니다. 각 수는 1,000 이하의 자연수입니다.

📊 출력

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

---

🔍 풀이 과정

소수의 정의

소수는 1과 자기 자신만을 약수로 가지는 수를 말합니다. 즉, 주어진 숫자가 소수인지 판단하려면, 그 수를 2부터 자기 자신 - 1까지 나누어떨어지는지 확인해야 합니다.

핵심 아이디어

1. 입력받은 수 중 2보다 작은 수는 소수가 아니므로 제외합니다.
2. 각 수를 2부터 자기 자신보다 작은 수까지 나누어보고, 나누어떨어지는 수가 없으면 그 수는 소수입니다.
3. 제곱근까지만 계산하면 소수 여부를 더 효율적으로 판정할 수 있지만, 이번 문제에서는 입력 크기가 작아 단순한 방식으로도 충분히 해결할 수 있습니다.

---

🔨 코드 구현

a = int(input())  # 수의 개수를 입력.
numbers = list(map(int, input().split()))  # N개의 수를 리스트로 입력.
count = 0  # 소수의 개수를 저장할 변수

# numbers 리스트에 있는 각 수에 대해 소수 여부를 확인
for i in numbers:
    if i < 2:  # 2보다 작은 수는 소수가 아니므로 제외
        continue
    for j in range(2, i):  # 2부터 i-1까지의 수로 나누어봄
        if i % j == 0:  # 나누어떨어지면 소수가 아님
            break
    else:  # 끝까지 나누어떨어지지 않으면 소수
        count += 1

print(count)  # 소수의 개수를 출력

---

🚀 코드 설명

1. 첫 줄에서 input()을 통해 수의 개수를 입력받습니다. 그다음 map(int, input().split())으로 입력된 수들을 공백으로 구분하여 리스트로 저장합니다.
2. for문을 통해 리스트의 각 수를 반복하면서 소수 여부를 판정합니다.
   • 2보다 작은 수는 소수가 아니므로 제외합니다.
   • 그 이상의 수에 대해 2부터 자기 자신 - 1까지 나누어떨어지는지 확인합니다. 나누어떨어지면 소수가 아니므로 break로 루프를 탈출하고, 그렇지 않으면 소수 개수를 1 증가시킵니다.
3. 마지막으로 소수의 개수를 print()를 통해 출력합니다.

---

🧐 배운 점

이 문제를 풀면서 다시 한 번 소수 판별 알고리즘에 대해 정리할 수 있었습니다. 제곱근까지만 확인해도 소수 판별이 가능하다는 사실을 알고 있었지만, 문제의 범위가 작아 이번에는 단순히 반복문을 돌리는 방식으로 해결했습니다.

앞으로는 제곱근을 이용한 효율적인 소수 판별 알고리즘도 적용해보는 것을 목표로 삼아야겠다고 생각했습니다.

---

🔚 마무리

오늘 문제는 간단한 소수 판별 문제였지만, 기본적인 수학적 개념을 다시 복습할 수 있었습니다. 범위가 작은 문제에서는 단순한 방식도 충분히 사용 가능하지만, 더 큰 범위에서 성능을 고려한 알고리즘을 적용할 수 있는 연습도 중요하다는 것을 느꼈습니다.