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

백준#1929

바로가기

문제 해석
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성한다. 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

문제 접근
1. 소수를 구하는 함수를 만들어 사용한다.(하단 코드 참조)
2. M과 N 사이에 빈칸을 둔다 == map(int, input().split(" "))을 이용한다.

필요한 함수
①map(A함수, B집합)
==(개념) 파이썬의 내장함수로서, map 이하의 B집합(리스트, 문자열)에 A함수를 적용하는 것이다. A과 B 둘 다 반드시 채워져야 한다.
==(예시) map(int, input()) 👉 콘솔창에 input한 값에 int 함수를 적용한다. input의 경우 기본적으로 str이기 때문에, 수를 입력해서 연산하려면 int를 적용해야 한다.

코드

import sys
import math
def check(num):   ## 소수인지 체크하는 함수
    if num == 1:
        return False
    else:
        ## 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있으므로 하기 공식으로 구한다.
        for i in range(2, int(math.sqrt(num)+1)):
            if num%i == 0:
                return False
        return True
a,b = map(int, sys.stdin.readline().split(' ')) # 3 16
for i in range(a, b+1):
    if check(i):
        print(i)