[TIL] 작심 큰일 챌린지 미들러 코스 1일차 - 소수 구하기

 

 

소수 구하기 - 백준 1929번

 

난 분명 미들러 코스를 신청했는데 첫 날부터 소수 판별 문제가 나와서 처음에는 의아했다 

미들러 코스 치고는 난이도가 쉽다고 생각했기 때문 

 

그러나 풀면서 가장 들었던 생각은 이거 그대로 풀면 시간복잡도가 10 ^12 가 나오는데 이거 완탐으로 되려나? 였다

너무 만만하게 본 탓인가 보기 좋게 시간 초과로 틀려버렸다. 

 

 

'''
완전탐색으로 푼 시간 초과 코드 
'''

import sys
input = sys.stdin.readline

m,n = map(int, input().strip().split())


def is_prime(num):
    for i in range(2,num):
        if num % i == 0:
            return False
    return True

          
for num in range(m, n+1):
    if is_prime(num):
        print(num)

 

 

알고보니 이 문제는 에라토스테네스의 체를 이용해서 문제에서주어진 범위 내의

소수의 배수를 하나씩 지워가며 푸는 문제 였다.

 

에라토스테네스의 체란 저런 식으로 체로 거르듯이 소수의 배수를 제거하고 

제거 되지 않은 수들을 소수로 취급하는 알고리즘이다. 

 

에라토스테네스의 체

 

 

 

 

 

내가 푼 정답 코드 

 

 

1. 인덱스를 사용해서 풀기위해 n+1 크기의 배열을 만들어주고 모든 수를 True(소수)로 초기화 해준다.

2. 0과 1은 소수가 아니니 False로 초기화 

3. 2부터 for문을 돌며 제곱근 까지의 범위만 확인하면서 i를 제외한 i의 모든 수를 소수가 아니라고 해준다

4. 문제에서 주어진 범위내에 있는 소수들을 출력해준다. 

 

import sys, math
input = sys.stdin.readline

m,n = map(int, input().strip().split())


prime = [True for _ in range(n+1)] #처음에는 모든 수가 소수인 것으로 초기화 
prime[0] = False
prime[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
    if prime[i]: # i가 소수라면
        #i를 제외한 i의 모든 배수를 지움(=소수가 아니라고 해줌)
        for j in range(i+i, n+1, i):
            prime[j] = False

for i in range(m,n+1):
    if prime[i]:
        print(i)

 

시니어 코드 

 

사실 작심큰일 챌린지를 시작하기 전에 가장 기대됐던 것이 시니어 개발자의 해설이 주어진다는 것이었는데 

역시 시니어의 코드를 보니 내 코드랑 차원이 달랐다... 

 

N, M = map(int, input().split())

for i in range(N, M + 1):
    if i == 1:
        continue
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

 

 

처음에는 2~n-1까지가 아니라 왜 √n 까지만 보면 되는 건지 이해가 잘 안갔는데 해설을 보니 

어떤 수 n 이 두 수의 곱으로 표현 될 수 있다면 그 중 하나는 반드시 √n 이하에 있기 때문에 √n까지만 나눠지는지 체크해도 전혀 문제가 안된다는 것이었다! 

 

길이도 길이지만 내가 푼 방법대로 하면 n+1 칸의 메모리 비용이 발생했는데 그 단점이 없어진게 큰 것 같다. 

그리고 파이썬에만 적용되는 for-else 문법을 알게된 것이다. 

 

break 없이 반복문이 끝나면 바깥의 else 문이 실행되는 구조다. 

따라서 이 문제는 소수 판별 + 반복문 활용 + 파이썬 문법이 어우러진 문제였다. 

 

단순한 문제인줄 알았더니 이 문제에서 배워갈 수 있었던게 많았던 것 

 

 

차이점 정리 ) 

1. n+1 칸의 배열을 선언하지 않고 바로 M~N 범위를 for 문으로 돌면서 검사 

2. math 라이브러리를 사용하지 않고 i**0.5 

3. 1은 소수가 아니므로 배열에 False 처리 하는 대신 continue로 넘김 

4.  for-else로 조건 처리 깔끔하게