[백준] 1929 - 소수 구하기 (Python)

민영·2022년 1월 4일

백준 알고리즘

[Algorithm] 백준

목록 보기

16/31

문제

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

제출 코드

import math

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N + 1):
    if isPrime(i):
        print(i)

결과

정리

개념

소수인지 아닌지 판단하려면 보통 2부터 비교하는 숫자까지 하나씩 나눠가면서 나머지를 확인해야된다. 하지만 비교하는 숫자의 제곱근까지의 수만 확인해도 소수인지 아닌지 판단할 수 있다.

예시1) 15는 소수인가!
15의 제곱근은 3.xxx이니까 15를 2와 3으로만 나눠보고 소수인지 아닌지 판단할 수 있다는 뜻이다. 실제로 15는 2로는 안나눠지지만 3으로는 나눠지기 때문에 소수가 아닌 것이다!
예시2) 17은 소수인가!
17의 제곱근은 4.xxx이니까 17을 2, 3, 4로만 나눠보고 소수인지 판단한다는 뜻이다. 실제로 17은 2, 3, 4로 나누었을 때 모두 나누어떨어지지 않는다. 따라서 17은 소수인 것이다!

주석있는 코드

import math

# 소수인지 아닌지 판단하는 함수
def isPrime(num):
    # 1은 소수가 아니므로 건너뛴다
    if num == 1:
        return False

    else:
        # ('비교하려는 수 = num'의 제곱근을 int로 바꾼것) + 1 만큼으로 범위를 지정해준다
        for i in range(2, int(math.sqrt(num) + 1)):
            # 나누어지면 소수가 아니다
            if num % i == 0:
                return False
        return True

# 입력받기
M, N = map(int, input().split())

# M이상 N이하의 소수를 구하는 것이므로 N+1로 설정한다
for i in range(M, N + 1):
    # True이면 소수라는 뜻이므로 출력한다
    if isPrime(i):
        print(i)