파이썬으로 백준 1978번 소수 구하기

백준 1978번 문제는 소수 구하기이고 파이썬으로 풀 때 주의사항이 있습니다.

다른 언어와 달리 파이썬에서 주의해야 될 부분이 바로 for문에 range를 쓰는 경우인데요.

이 부분을 유념하면서 백준 1978번을 풀어보겠습니다.

백준 1978번 파이썬 코드

먼저 제가 작성한 백준 1978번 파이썬 코드부터 보여드리겠습니다.

반응형

def isPrime(n):
    if n == 1:
        return False
    for i in range(2,n//2 + 1):
        if n % i == 0:
            return False
    return True
N = int(input())
nums = list(map(int,input().split()))
cnt = 0
for i in nums:
    if isPrime(i):
        cnt += 1
print(cnt)

isPrime 함수는 파이썬에서 정수를 입력받아 소수 여부를 리턴해주는 함수로 작성했습니다.

N에서 input을 받는데 파이썬에서는 크게 의미 없으니 넘어가고 nums에 list 형태로 숫자를 파싱 해서 넣어줍니다.

작성된 소스와 같은 방식으로 파싱해서 입력하는 방법은 블로그 내 카테고리 파이썬을 참고해주시길 바랍니다.

cnt는 소수 개수를 입력하기 위한 변수이며, 입력된 정수형의 리스트를 순회하면서 작성한 isPrime 함수로 확인한 뒤 소수이면 cnt에 1을 더해줍니다.

아래의 내용에서 소수 구하는 isPrime 함수를 자세히 살펴보겠습니다.

반응형

파이썬 소수구하기

제가 구현한 isPrime이라는 함수는 파이썬에서 소수를 구하는 함수입니다.

n이 1인 경우 백준 1978번 문제에서 주어진 것을 보시면 아시겠지만 1은 소수가 아니기 때문에 False로 리턴합니다.

그 외의 경우 2부터 자기 자신의 절반까지 수로 나누어보면서 나누어지는 경우 False로 리턴하고 나누어지지 않는 경우 True로 리턴합니다.

여기서 range 변수를 2부터 시작하는 이유는 1이 나눗셈의 항등원이기 때문에 모든 수를 False로 출력하는 걸 방지하기 위함입니다.

n//2 + 1까지로 선언한 이유가 바로 파이썬에서 백준 1978번 소수 구하기 문제를 푸는 핵심입니다.

N까지 반복하지 않는 이유

N까지 반복해서 나누어봐도 충분히 결과는 일치하게 나옵니다.

그러나 N//2 + 1까지만 반복하는 이유는 속도 측면에서 굳이 그럴 이유가 없기 때문입니다.

참고로 N//2는 파이썬의 정수 나누기 연산자로 N의 절반보다 작거나 같은 최대 정수 즉 가우스 값을 구해줍니다.

예를 들어 11의 소수 여부를 판별한다고 봅시다.

11을 2로 나누고 3으로 나눕니다. 여기서 4로 나누어볼 이유는 없습니다. 왜냐하면 4와 4보다 큰 어떤 정수를 곱했을 때 11보다 클 수밖에 없기 때문이죠.

반응형

그래서 정확히 말하면 수학적 측면에서 볼 때 N의 절반이 아닌 제곱근보다 작은 최대 정수까지만 확인해도 됩니다.

다만 파이썬에서는 제곱근을 구하는 math 함수를 쓰는 것보다 2로 나누는 편이 간편하기도 하고 백준 1978에서 제안해주는 수가 1000 이하라 큰 차이를 보이지 않을 것으로 보여 절반까지만 확인하도록 코딩했습니다.

마지막으로 + 1을 붙인 이유는 파이썬에서 range 변수 end값은 반복에 들어가지 않기 때문입니다.

 

사실 이것도 n//2 - 1이 n의 제곱근보다 큰 경우는 거의 없다고 볼 수 있기 때문에 필요 없다고 생각할 수 있지만 예외가 있습니다. 바로 4입니다.

4가 n으로 들어오는 경우 n//2는 2가 되기 때문에 반복 자체를 안 하고 True를 리턴합니다.

그러니까 최종적으로 파이썬 소수 구하기 백준 1978번 문제를 풀 때 조심해야 될 예외는 1과 4 총 두 가지라고 정리하면서 글을 마무리합니다.