• TOC {:toc}

이 글은 백준 온라인 저지의 2581번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 풀이를 같이 기록합니다. 필요한 경우 풀이에 대한 해설을 기록합니다만 풀이는 통과했어도 해설은 정답이 아닐 수 있어서 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.03.30

메모리 시간 코드 길이
28776 KB 76 ms 281 B 
M = int(input())
N = int(input())
p = []

# M ~ N까지의 수 중에서
for n in range(M, N + 1):
    r = int(n ** 0.5) + 1
    # 2부터 주어진 수의 제곱근 까지의 수로
    for i in range(2, r + 1):
        # 나눴을 때 나누어 떨어지는 수가 있으면
        if n % i == 0:
            # 반복을 중단.
            break
    # 입력한 수가 1이 아니고, 위의 반복이 중단되지 않았으면
    if n != 1 and i == r:
        # n을 소수 리스트에 추가한다.
        p.append(n)
if len(p) == 0:
    print(-1)
else:
    print(sum(p))
    print(p[0])

아이디어 & 풀이

입력 받은 범위의 수에 대해서 각 수의 소수 여부를 조사한다.

  • 2부터 현재 값의 제곱근 까지의 수를 순회하면서 현재 값을 나눴을 떄 나누어 떨어지는 경우가 있으면 반복이 중단된다.
  • 현재 값이 소수면 반복이 중단되지 않고,
  • 반복이 중단되지 않았다면 반복이 반복이 끝났을 때 순회한 변수(i)의 값이 반복 범위의 끝인 r과 같아야 한다.

위의 조건을 만족하는 수를 소수 리스트에 추가한다.

  • 1은 소수가 아니기 때문에 예외 처리를 해줘야 한다.

제곱근 값을 int로 바꾸면 소수점 이하를 버리기 때문에 r = int(n ** 0.5)로 하면 n이 2나 3일 때 반복문에 진입하지 못해 실행이 제대로 되지 않는다.

  • r = int(n ** 0.5) + 1로 해주었는데 차라리 2와 3을 따로 예외 처리를 하는 게 더 깔끔할 수도 있을 것 같다.

참고 답안

M = int(input())
N = int(input())

# 1 ~ N까지의 수에서 소수 번째 index의 원소만 True로 남겨놓은 리스트를 미리 만들어놓는다.
a = [False, False] + [True] * (N - 1)
r = int(N ** 0.5)
# 2 ~ r까지의 수에서
for i in range(2, r + 1):
    # a[i] 값이 True인 것 중에서
    if a[i]:
        # i의 배수인 j의 arr[j]를 False 처리
        for j in range(2 * i, N + 1, i):
            a[j] = False

# m ~ n까지의 i 중에서 arr[i]가 True인 i로 배열 구성
p = [i for i in range(M, N + 1) if a[i]]

if len(p) == 0:
    print(-1)
else:
    print(sum(p))
    print(p[0])

아이디어 & 풀이

주어진 수까지 해당 인덱스의 소수 여부를 (True, False) 값으로 갖는 리스트를 만든다.

  • 리스트를 초기화할 때 연산 기호를 이용해 리스트의 원소를 합치거나 특정 원소를 여러 개로 반복할 수 있다.

주어진 수의 제곱근까지 순회하면서 각 수의 배수 인덱스의 값을 False로 바꾼다.