[항해]알고리즘 스터디(백준 #1929)

백준#1037 - ACM 호텔

바로가기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입출력 규칙

1. 입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
2. 출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

문제 접근

1. 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다고 하였기 때문에, map함수를 이용하여 두 자연수를 입력받는다.
2. 우리가 원하는 출력은 입력한 두 자연수(M, N 포함) 사이의 소수를 구해 나열하는 것이다.
3. 이를 위해선 소수를 구하는 것이 선행되어야 한다.
4. 소수를 구하는 함수는 아래와 같다.

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

4-1. 중요한 부분은 for문이다. 소수를 구할 때는 입력받은 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있게 된다.
4-2. 즉, 이 함수를 통해 소수면 True, 그 외(입력값이 1인 경우와 num % 1 == 0)의 경우 False를 반환한다.
5. 문제 조건에서처럼 두 개의 입력값(M과 N) 사이의 소수를 구하는 것이므로, M~N 사이의 수를 반복하는 반복문을 작성하고, 위 함수를 거치게 한다.
6. 그 결과가 True일 경우의 수만 출력하면 되겠다.

코드

import math

a, b = map(int, input().split())


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


for i in range(a, b + 1):
    if check(i) == True:
        print(i)