1929_소수구하기

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

 

사실 이전에 했던 소수구하기대로 하면 될줄 알았으나, 입력값이 1000000까지 되어서 안되었다. 고민을 하다가 결국 인터넷의 도움을 조금 받았는데 신기하게 내가 소수문제를 맨 처음에 풀었던 방식으로 풀었다.

 

나는 소수첫번째문제(2581번) 문제를 풀때 lst에 모든 값을 저장하고, 소수들을 제거하는 방식을 사용했는데, 이 방식을 훨씬 세련되게 쓰는 방식이 있었다.

 

m,n = map(int,input().split())
lst = [True]*(n+1)
n+=1

for i in range(2,int(n**0.5)+1):
    if lst[i]:
        for j in range(2*i,n,i):
            lst[j] = False


for i in range(m,n):
    if i>1 and lst[i] == True:
        print(i)

다만, 방식이 그대로여도 소수를 검사할때 1부터 100까지 검사한다고 치면, 100까지가아닌, 10까지만 소수를 검사한 후에, 그 배수들을 날려버리는 방식으로 해도 된다는거에 놀랐다. 

 

자세한건 아래 글을 읽어보는것이 효율적일 것 같다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4