[파이썬(Python)] 백준 1978번 소수 찾기

 

 

백준 1978번 소수 찾기

문제 바로 가기

---

📌 문제

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

 

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

 

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

 

 

 

📝 문제 접근 방법

아이디어

주어진 수에 대해 제곱근까지만 나눗셈을 수행하여 소수를 판별

 

• 소수 (Prime Number)
  • 1과 자기 자신만으로만 나누어떨어지는 자연수
  • 즉, 1보다 크고 다른 수로 나누어떨어지지 않는 수

 

• 완전 탐색 방법
  • 방법
    • 숫자 n을 2부터 n - 1까지의 모든 숫자로 나누어봅니다.
    • 나눠떨어지는 숫자가 하나라도 있다면 n은 소수가 아닙니다.
    • 나눠떨어지는 숫자가 없으면 소수로 판별합니다.
  • 문제점: n - 2번의 나눗셈을 수행해야 하므로 숫자가 커질수록 연산량이 매우 많아집니다.

 

• 제곱근까지만 확인하는 방식
  • 원리: 어떤 수 n이 합성수라면 두 인수(a, b)를 곱한 형태로 나타낼 수 있습니다.
    • $n = a \times b$
    • 여기서 두 인수 중 하나는 반드시 $\sqrt{n}$ 이하입니다. 
      • 만약 인수 a와 b가 모두  $\sqrt{n}$ 보다 크다면 $a \times b > n$ 이 되므로 불가능합니다.
  • 이유
    • 모든 약수쌍 (a, b)에서 작은 인수는 $\sqrt{n}$ 이하에 속합니다.
    • 큰 인수는 작은 인수의 대칭 쌍이므로 이미 확인한 범위에 포함됩니다.

 

 

 

👩‍💻 나의 답안

import math

def is_prime_number(x):
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

n = int(input())
numbers = list(map(int, input().split()))

result = sum(1 for num in numbers if is_prime_number(num))
print(result)

 

 

 

✨ 새로 알게 된 점

1. 소수 판별의 효율적인 방식과 원리

소수를 판별할 때, 모든 수를 확인하는 대신 제곱근까지만 탐색하면 충분하다는 점을 알게 되었습니다. 모든 약수쌍 (a, b) 중 하나는 항상 $\sqrt{n}$ 이하에 존재하기 때문에, 2부터$\sqrt{n}$ 까지만 나눗셈을 수행해도 소수 여부를 정확히 판별할 수 있습니다. 이는 약수의 대칭적 관계를 활용한 방식으로, 불필요한 연산을 크게 줄여 효율성을 높일 수 있었습니다.