(BOJ)-1978, Python

문제 요약

출처: (BOJ)1978 - 소수 찾기

$N$만큼 수가 주어졌을 때, 소수가 몇 개인지 출력하는 문제이다.

접근 과정

1. 완전탐색 접근

1과 자신만을 약수로 가지고 있으면 되니, 아래와 같이 간단하게 작성할 수 있었다.

코드 구현

N = int(input())
numList = list(map(int, input().split()))

count = N
for num in numList:
    if num == 1:
        count -=1
        continue
    for i in range(2, num):  
        if num % i == 0:
            count -= 1
            break
print(count)         

2. 정수론 최적화

위 코드에서 $1$부터 $n-1$까지의 탐색을 통해 소수임을 판별했지만, 이 코드의 탐색 범위를 약수의 대칭성을 이용하면 줄일 수 있다. 예를 들어 $12$이라는 숫자를 아래와 같이 표현할 수 있다.

• $1\times12 = 12$
• $2\times6 = 12$
• $3\times4 = 12$
• $4\times3 = 12$
• $6\times2 = 12$
• $12\times1 = 12$

위 절반 $3\times4$ 까지만 구해도 $12$의 모든 약수를 우리는 구할 수 있기에, 약수의 대칭성을 이용한 소수판별에는 이러한 결론을 내릴 수 있을 것 같다.

• 만약 $n$이 소수가 아니면, $n$의 약수 중 적어도 하나는 $\sqrt{n}$​ 이하에 있다.
• 반대로 소수면 $\sqrt{n}$​ 안에 약수가 $1$밖에 없다.

따라서 $\sqrt{n}$​까지만 검사하면 되기에 계산량을 크게 줄여준다는 것이다!

코드 구현

N = int(input())
numList = list(map(int, input().split()))

count = N
for num in numList:
    if num == 1:
        count -=1
        continue
    for i in range(2, int(num**0.5)+1): #재구성된 부분
        if num % i == 0:
            count -= 1
            break   
print(count)

회고

최적화까지 요구되는 문제는 아니지만, 아이디어가 내 기준에선 재밌게 느껴졌기에 추가하였다. 그리고 count를 세는 문제에서 오히려 줄여가는 방향으로 코드를 짜보니 뭔가 코드가 더 간결해진 것 같다..!