[Python] Baekjoon1929: 소수 구하기

소수 구하기

2 초

256 MB

144301

40448

28581

26.802%

문제

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

입력

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

출력

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

풀이

인덱싱이 핵심입니다. 크기가 [N]인 배열형 리스트를 만듭니다.

M, N = list(map(int,input().split()))
prime = [True for i in range(N+1)] # N+1 크기의 배열형 리스트 완성

 

방식

M부터 시작해서 N까지 현재 숫자의 배수를 모두 배열에서 지워버리는 방식입니다. 예를 들어 2부터 시작할 때, 2를 제외한 2의 배수인 4, 6, 8, 10...은 모두 2의 배수이므로 소수가 아닙니다. 즉 현재 탐색하는 i에 대해서 i를 제외한 배수를 모두 소수가 아니라는 표시를 해줍니다.

def checkPrime(num):
    n = num*2 # 초기 시작값은 i의 2배부터
    while n <= N: # N이하까지만 표시
        prime[n] = False # 소수가 아니라고 표시
        n += num

 

탐색 범위

i라는 숫자의 배수를 모두 찾아내 소수가 아니라는 것을 체크하고 있습니다. 하지만 i를 제외한 ix2부터 체크해주기 때문에 끝값 N이 만약 1000이라면 i가 501일 때 굳이 2를 곱해서 체크해줄 필요는 없습니다. 그렇기 때문에 탐색 범위는 N을 2로 나눈값보다 커졌을 때 소수를 찾을 필요가 없으므로 탐색범위는 M부터 N/2 까지입니다.

for i in range(2,N//2+1):
    if prime[i]:
        checkPrime(i)

 

주의점

M과 N은 1부터 시작하므로 1은 시작값에서 빼주어야 합니다.

prime[1] = False

 

전체코드

M, N = list(map(int,input().split()))
prime = [True for i in range(N+1)] # N+1 크기의 배열형 리스트 완성
prime[1] = False
def checkPrime(num):
    n = num*2
    while n <= N:
        prime[n] = False
        n += num

for i in range(2,N//2+1):
    if prime[i]:
        checkPrime(i)

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