[백준 1929] 소수 구하기

1. 링크

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

2. 문제 설명

1) 문제

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

 

2) 입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

3) 출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

3. 코드

#1929

import math

#소수 판별 함수 정의
def Is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0: return False
    return True

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

#소수일 경우 primes에 추가
for i in range(M, N+1):
    if Is_prime(i) and i!=1:
        primes.append(i)

#결과 출력하기
for n in primes: print(n)

4. 설명

자주 나오는 문제 유형인 소수 판별이다. 관련 개념이 부족해 문제를 풀기 위해 다음 블로그를 다수 참고하였고, 때문에 코드도 매우 유사하다..

[알고리즘] 소수의 판별 - 에라토스테네스의 체

특정 자연수가 소수인지 확인하기 위해선 제곱근까지만 (가운데 약수까지만) 확인하면 충분하다. 이는 가운데 약수를 기준으로 약수와 약수를 곱해 자연수를 구하는 등식이 대칭적이기 때문이다. 이를 통해 연산 횟수를 줄일 수 있고, 나 또한 이 방법을 사용하였다.

우선 소수 판별 함수를 정의하고, 입력을 받은 후 입력 범위 사이의 자연수들에 대해 소수일 경우 primes 리스트에 append하였다. 그 후 결과를 출력하면 된다.

시간복잡도는 O(N)이다.

 

5. 배운 점

우선 소수 판별 알고리즘에 대해 잘 정리된 블로그글을 찾아 확실하게 개념을 잡았고, 이후 다른 문제는 자력으로 풀 수 있을 것 같다. 또한 처음 코드에서는 1을 제외하는 처리를 하지 않아 틀렸는데, 이런 류의 문제를 풀 때 1은 소수가 아니라는 점을 확실히 해야 한다고 다짐했다.