[python]백준_1456 : 거의 소수

Choco Ham·2022년 10월 13일

algorithm python 백준

algorithm

목록 보기

5/6

🚗현대인을 위한 3줄요약.

에라토스테네스의 채를 이용하여 소수관련 문제를 쉽고 빠르게 해결할 수 있다.

📌전체코드

문제 링크 : https://www.acmicpc.net/problem/1456

우선 전체 코드는 다음과 같다.

import sys, math
input = sys.stdin.readline

m, n = map(int, sys.stdin.readline().split())

primeList = [True] * (int(n ** 0.5) + 1)
primeList[1] = False

for i in range(2, int(n ** 0.5) + 1):
    if primeList[i]:
        if i * i > int(n ** 0.5):
            break
        for j in range(i**2, int(n ** 0.5) + 1, i):
            primeList[j] = False

count = 0
for i in range(1, len(primeList)):
    if primeList[i]:
        res = i * i
        while True:
            if res < m:
                res *= i
                continue
            if res > n:
                break
            res *= i
            count += 1

print(count)

해당 코드에서 면밀히 살펴볼 부분은 다음과 같다.

primeList[] : 소수를 판별하는 기준. True일 경우 소수이고 False일 경우 소수가 아니다.
for문 : 소수를 계산하는 식.

각 키워드가 포함된 문단별로 나눠서 분석해보자

👉primeList[]

primeList[]는 소수를 판별하는 기준이 되는 list로 각 자리의 숫자가 True일 경우 소수, False일 경우 소수가 아니라고 볼 수 있다. primeList[]의 소스코드를 해석하기 위해선 우선 에라토스테네스의 채에 관한 선행이 필요하다.

에라토스테네스의 채는 효과적으로 소수를 판별하는 알고리즘으로 주어진 범위에서 합성수를 지우는 방식으로 진행된다. 자세한 방법은 다음과 같다.

소수가 아닌 1은 미리 제거한 후 가장 작은 소수인 2를 선택한다.
선택된 소수( = 2 )의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 숫자( = 3 )을 소수로 선택한 후 선택된 소수의 배수를 모두 지운다.
위와 같은 과정을 반복한다.

기존의 소수를 판별하는 방법에 비해 에라토스테네스의 채가 갖는 이점은 시간복잡도에 있다. 미리 소거한 수에 대해서는 계산을 진행하지 않기 때문에 모든 수를 한번씩 검사하는 기존의 방법보다 훨씬 효율적이라 볼 수 있다.

다시 돌아와서 에라토스테네스의 채에서 사용되는 모든 수를 저장한것이 primeList[]이다.

primeList = [True] * (int(n ** 0.5) + 1)
primeList[1] = False

처음에는 모든 수를 소수로 가정하기에 모두 True로 입력한다. 이때 n의 약수는 (n ** 0.5) 이하이기 때문에 전체 수가 아닌 (n ** 0.5)까지 계산하면 시간을 더 아낄 수 있다. 또한 1은 소수가 아니기 때문에 선언단계에서 미리 False로 값을 지정해준다.

👉for문

primeList[] 작성이 끝났다면 for문 안에서 소수를 판별할 차례이다.

for i in range(2, int(n ** 0.5) + 1):
    if primeList[i]:

1은 소수가 아니기 때문에 2부터 시작하여 n의 제곱근까지 primeList[]를 탐색한다. 만약 primeList[i]가 True라면 다음과 같은 조건문에 진입한다.

        if i * i > int(n ** 0.5):
            break
        for j in range(i**2, int(n ** 0.5) + 1, i):
            primeList[j] = False

(i * i)가 n의 제곱근보다 큰지 확인하고 그렇다면 break, 그렇지 않다면 i^2부터 n의 제곱근까지의 수를 모두 False로 치환한다.

이렇듯 채에 거르듯이 모든 숫자를 에라토스태네스의 채 알고리즘으로 거르고 나면 primeList[]에는 소수와 소수가 아닌 것들이 True와 False로 구분되게 된다.

👉primeList[]로 거의소수 구하기

소수 판별이 완료되었다면 문제에서 요구하는 거의 소수를 구할 차례이다. 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 따라서 거의 소수를 구하기 위해선 primeList[]에서 True에 해당하는 숫자를 이용하면 된다.

count = 0
for i in range(1, len(primeList)):
    if primeList[i]:
        res = i * i

거의 소수의 개수를 대표하는 변수 count를 0으로 초기화한 후 primeList[i]가 True인 경우에 한해서 i^2와의 비교작업에 들어간다.

        while True:
            if res < m:
                res *= i
                continue

만약 res( = i^2 )가 주어진 범위(m)보다 작다면 res에 i를 제곱한 후 continue 한다.

            if res > n:
                break
            res *= i
            count += 1

print(count)

그렇지 않다면(주어진 범위 내라면) 또다시 res가 주어진 범위 n에 해당하는지 검사한다. 범위 밖인 경우. 즉 계산이 끝난 경우 break를 진행, 거의 소수의 개수인 count를 출력한다. 그렇지 않을 경우(주어진 범위 내라면) res에 i를 제곱한 후 count를 1 증가시키고 이를 반복한다.

📌다른 방법

같은 에라토스테네스의 채를 사용하더라도 거의 소수를 구하는 방법에 따라 정답이 될 수도, 오답이 될 수도 있다. 아래 코드는 처음 이 문제를 풀었을 때 제출한 코드이다.

# 메모리 초과
# 
# ~~~ 에라토스태네스의 채 코드 ~~~


arr = [i for i in range(2, n + 1) if primeList[i] == True]

count = 0
for i in arr:
    for j in range(2, len(arr)):
        if i ** j > n:
            break
        else:
            count += 1

print(count)