[백준] 1929번 소수 구하기 [Python]

 

M이상 N이하의 소수를 모두 출력

 

문제

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

입력

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

출력

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

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

 

에라토스테네스의 체 -

크기가 작은 소수 순서대로 그 소수의 배수를 제거해 나가는 방식

위 과정을 통해 합성수는 제거되고 소수만 남게 됩니다.

import sys
def f(M,N):
    li = [False,False,True]+[i%2 for i in range(3,N+1)]
    for n in range(3, N+1, 2):
        if li[n]:
            li[n*n::n] = [False]*(N//n-n+1)
    return li[M:]

M, N = map(int, sys.stdin.readline().split())
li = f(M,N)
print("\n".join([str(n) for n, t in zip(range(M,N+1),li) if t]))

 

소수인지 확인하는 함수를 통해 푸는 방법

주어진 자연수 N에 대해서

2부터 N의 양의 제곱근 이하의 자연수까지의 수로 N을 나눌 때

나누어 떨어지면 N은 합성수, 아니면 소수로 판별 함

 

import sys

def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    print(n)

M, N = map(int, sys.stdin.readline().split())
for n in range([M+1-M%2,2][M==2], N+1):
    if n == 1:
        continue
    isprime(n)

 

예제 입력 1 

3 16

예제 출력 1 

3
5
7
11
13