[백준] 1929번 - 소수 구하기 by Python(파이썬)

✨ 문제

문제 링크 → 백준 1929번 - 소수 구하기

✨ 주의할 점

• 소수에 1은 포함되지 않는다. (이것 때문에 이번에 첫 번째 제출했을 때 틀렸다..ㅜㅜ)

✨ 풀이

제일 처음 생각한 풀이

import math

M, N = map(int, input().split())
if M == 1: M += 1 # 1은 소수가 될 수 없으므로 제외
for i in range(M, N+1): # M~N까지 반복
    flag = True 
    for j in range(2, int(math.sqrt(i)+1)): # 조금이라도 시간 단축하기 위해 제곱근 사용
        if i % j == 0: # 한 번이라도 j에 의해 나눠 떨어지면 flag=False & break
            flag = False
            break
    if flag: # 반복문을 다 돌고 빠져나오면 flag=True인 상태 → 소수
        print(i)

제출 후 다시 생각해본 풀이

M, N = map(int, input().split())
nums = [1]*(N+1)
nums[0] = 0
nums[1] = 0

for i in range(2, int(N**0.5+1)):
    if nums[i]:
        j = 2
        while i*j <= N:
            nums[i*j]=0
            j+=1
for i in range(M, N+1):
    if nums[i]:
        print(i)

• 백준 1241번 설명 에서 시간 단축한 풀이가 있는데, 그 방식과 비슷하게 다시 작성한 코드이다.
• 굳이 M~N까지의 수들에 대해서 소수인지 확인하는 것이 아니라, 0~N까지의 수에 대해서 0, 1은 소수가 아니라는 의미로 0을 nums 리스트에 저장하고 2부터 N**0.5+1까지의 수에 대해 nums[i]가 1이면(소수이면) N보다 작거나 같은 i의 배수들에 소수가 아니라는 의미로 0을 대입해주는 것이다.
• 마지막으로 M~N 범위의 nums 리스트에서 값이 1인 인덱스를 출력해준다. (소수 리스트)

✨ 결과

첫번째 풀이

두번째 풀이

👩🏻‍💻 후기

이 문제는 1년 전에 도전했다가 틀리고 냅뒀던 문제인데,, 이번에 못 풀었던 문제들 하나씩 풀어가면서 다시 풀게 된 문제이다. 이번에 알고리즘 수업을 들어서인지 이 문제는 3분??만에 푼 것 같다. 그리고 최대한 시간을 줄여보고 싶어서 내 기준으로 제일 먼저 생각난 제곱근,,을 사용해봤다. 제출한 후에는 바로 직전에 풀었었던 1241번에서 시간 단축한 풀이에서 사용한 방식과 비슷하게 생각해 다시 풀었었다. 시간 단축이 정말 많이 되었다,, 아무래도 첫번째 풀이는 O((N-M+1)*(int(sqrt(i)+1)-2)) 시간복잡도를 가지는 반면, 두번째 풀이는 O(N-M+1)이나 그 위 반복문이 가지는 시간복잡도를 취하기 때문에 더 빠르지 않나 싶다. ((핵심은 첫번째 코드는 M부터 N까지의 수에 대해 매 반복에서 해당 수들이 소수인지 판별하는 것을 반복할 때 겹치는 부분이 존재하는 것이고 두번째 코드는 그렇지 않다는 것이다.))