기본수학2단계 소수구하기

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

문제 알아보기

문제

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

입력

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

출력

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

예제

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

---

문제 풀기

소수

소수(Prime Number)는 1을 제외한 양의 정수에서, 1과 자기자신만을 약수로 가지는 수를 의미한다.
예를들어 11은 1과 11을 곱해서만 만들 수 있기 때문에 소수이다..
또, 4는 14, 22 로 만들 수 있기 때문에 소수가 아니다.

에라토스테네스의 체

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

1을 제외하고 2부터 시작하여 구하고자 하는 수 end 까지 나열한 후, end의 배수를 나열한 리스트에서 모두 제외한다. 그렇게 E // 2의 배수들까지 모두 제외하면 남은 수는 모두 소수가 된다.

코드

start, end = list(map(int, input().split(' '))) #백준에서 정수 입력값 받기

#구하고자 하는 수 까지 나열한다. (end + 1)하여 end까지 포함하도록 한다.
arr = [True for i in range(end+1)] 

for i in range(2, end): #2부터 end까지 배수를 구한다.
    j = 2
    while i*j <= end:	#배수가 end를 넘지 않도록 한다.
        arr[i*j] = False
        j += 1

arr[1] = False #1은 소수에서 제외한다.
for i in range(start, end+1):#start부터 end까지의 소수 출력
    if(arr[i]):
        print(i)