백준 BOJ 1929번 소수 구하기 실버3 - Python 풀이

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

1929번: 소수 구하기

문제

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

입력

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

출력

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

 

소스 코드

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5) + 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)

 

어떤 수 N이 소수인지를 판별하는 방법은 N을 2부터 제곱근 N까지 나눴을 때 나누어 떨어지지 않는다면 소수이다.

제곱근 N까지 나누는 이유는 다음과 같다.

소수가 아닌 K를 두 수 곱으로 분해했을 때 두 수 중 작은 수가 최대가 될 때는 제곱 수일 때이기 때문이다.

 

에스테라토스 체 풀이를 사용하여 배열에 저장한다면 풀이를 더 최적화시킬 수 있다.

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

primes = [True] * (N + 1)
primes[0] = False
primes[1] = False

for i in range(2, int(N**0.5) + 1):
    for j in range(i * 2, N + 1, i):
        primes[j] = False

for i in range(M, N + 1):
    if primes[i]:
        print(i)

소수를 판별하는 로직 자체는 동일하다. (N을 2부터 제곱근 N까지 나눴을 때 나누어 떨어지지 않는다면 소수)

이전 풀이와 차이점은 나누는 연산을 거꾸로 곱하는 연산으로 바꾸어 계산한다는 것이다.

어떤 수 j가 어떤 수 i의 배수라면 소수가 아니기 때문에 아래서부터 하나씩 소수가 아닌 수를 지워나갈 수 있다.

1부터 N까지의 수 배열에서 2부터 제곱근 N까지의 배수들을 모두 지웠을 때 남아있는 숫자들은 모두 소수가 된다.