[백준/Python] 1929 : 소수 구하기

 

M과 N을 나란히 입력받은 후 이 사이에 존재하는 소수를 한 줄씩 출력하면 되는 문제이다.

 

일단 출력하는 형태를 통해 딱 M과 N 사이의 소수를 T/F로 구하는 함수를 만들어서 함수의 반환값이 True이면 list에 저장한 뒤, 최종적으로 리스트에 저장된 소수들이 크기 순서대로 저장되어 있으므로 원소를 순서대로 출력하면 될 듯 하다.

 

import math

M, N = map(int, input().split())
lst = []

def prime(x):
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True

for i in range(M, (N+1)):
    if prime(i) == True: lst.append(i)
for i in lst: print(i)

 

• prime이라는 함수를 만들어서 x가 2보다 작으면 (즉 1이면) 소수가 아니므로 False 반환
• 그 후 math 라이브러리의 sqrt (제곱근) 함수를 활용하여 루프에서 2부터 (루트 x + 1) 한 값 사이의 숫자들을 모두 지나가면서 현재 숫자인 x가 해당 범위 사이의 숫자와 나눠지는 값인지, 즉 소수가 아닌지를 판별한다.
  만약 여기서 나눠지는 i가 나온다면 x % i == 0 이 되어 소수가 아니므로 False 반환
• 위 두 단계를 모두 문제없이 통과했다면 소수이므로 True 반환 후 종료
• for 루프에서는 M과 N 사이의 범위의 모든 숫자(i)에 대해 prime 함수를 적용하고, 함수의 반환값이 True인 경우에만 리스트에 append 하여 저장한다.
• 최종적으로 리스트에 저장된 값들은 모두 소수이므로, 이를 for 루프를 이용하여 출력

 

맞긴 했는데 채점 시간이 오래 걸리는 것을 보니 효율적으로 짠 것 같지는 않아서 조금 더 검토해봐야겠다..!