BOJ 1978번 : 소수 찾기

안녕하세요. 지난 포스팅의 BOJ 2839번 : 설탕 배달에서는 복잡한 조건문을 걸어서 문제를 풀어보았습니다. 오늘은 소수를 찾는 기본적인 방법에 대해서 알아보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력
• 소수의 정의

 

제출 코드

N = int(input())
numbers = map(int, input().split())
cnt = 0
for number in numbers :
    flag = 1
    if number == 1 : continue
    for n in range(2, number // 2 + 1) :
        if number % n == 0: 
            flag = 0; break
    if flag == 1 : cnt += 1
print(cnt)

 

해설

입력 형식은 첫번째 줄에 입력되는 숫자의 개수 $N$, 두번째 줄에는 $N$개의 숫자들이 입력됩니다. 그리고 목표는 입력되는 숫자들 중 소수가 몇 개인지 출력하는 것이죠. 일단, 소수란 1과 자기자신 외에는 약수가 없는 1보다 큰 자연수를 의미합니다. 

 

따라서, 소수의 개수를 출력하기 위해서는 각 숫자들의 약수가 1이 아닌 다른 수가 존재하는 지 확인하면 되겠죠. 저희는 이를 두번째 반복문으로 구현하였습니다. 보시면 2부터 시작해서 number // 2 까지의 숫자들을 검사합니다. 모든 숫자들을 검사하지 않아도 되는 이유는 단순합니다. 어떤 수의 약수라는 것은 짝지어진 두 개의 자연수가 있음을 의미합니다. 따라서, 2로 나누어떨어지지 않는 다는 말은 2에 대응되는 number // 2 역시 나누어떨어지지 않는 다는 뜻이죠. 그래서 number보다 작은 숫자들 중 절반만 검사해주면 됩니다. 

 

이때, 검사할 때 하나라도 number에 약수가 존재하면 flag 변수를 0으로 바꾼 뒤 두번째 반복문을 탈출합니다. 그리고 해당 수는 소수가 아니기 때문에 cnt에 더해지지 않죠. 하지만, 약수가 하나라도 존재하지 않는다면 flag는 1로 유지되고 다음 조건문에 의해 소수로 판정되어 소수의 개수가 1이 늘어나게 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제