[python]백준_1456 : 거의 소수

📋 [ python ] 시리즈 몰아보기 (3)

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

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

📌전체코드

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

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

          
            
          
            1
            import sys, math
          
        

          
            2
            input = sys.stdin.readline
          
        

          
            3
            
          
        

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

          
            5
            
          
        

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

          
            7
            primeList[1] = False
          
        

          
            8
            
          
        

          
            9
            for i in range(2, int(n ** 0.5) + 1):
          
        

          
            10
                if primeList[i]:
          
        

          
            11
                    if i * i > int(n ** 0.5):
          
        

          
            12
                        break
          
        

          
            13
                    for j in range(i**2, int(n ** 0.5) + 1, i):
          
        

          
            14
                        primeList[j] = False
          
        

          
            15
            
          
        

          
            16
            count = 0
          
        

          
            17
            for i in range(1, len(primeList)):
          
        

          
            18
                if primeList[i]:
          
        

          
            19
                    res = i * i
          
        

          
            20
                    while True:
          
        

          
            21
                        if res < m:
          
        

          
            22
                            res *= i
          
        

          
            23
                            continue
          
        

          
            24
                        if res > n:
          
        

          
            25
                            break
          
        

          
            26
                        res *= i
          
        

          
            27
                        count += 1
          
        

          
            28
            
          
        

          
            29
            print(count)

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

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

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

👉primeList[]

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

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

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

eratostenes

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

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

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

          
            2
            primeList[1] = False

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

👉for문

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

          
            
          
            1
            for i in range(2, int(n ** 0.5) + 1):
          
        

          
            2
                if primeList[i]:

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

          
            
          
            1
                    if i * i > int(n ** 0.5):
          
        

          
            2
                        break
          
        

          
            3
                    for j in range(i**2, int(n ** 0.5) + 1, i):
          
        

          
            4
                        primeList[j] = False

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

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

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

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

          
            
          
            1
            count = 0
          
        

          
            2
            for i in range(1, len(primeList)):
          
        

          
            3
                if primeList[i]:
          
        

          
            4
                    res = i * i

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

          
            
          
            1
                    while True:
          
        

          
            2
                        if res < m:
          
        

          
            3
                            res *= i
          
        

          
            4
                            continue

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

          
            
          
            1
                        if res > n:
          
        

          
            2
                            break
          
        

          
            3
                        res *= i
          
        

          
            4
                        count += 1
          
        

          
            5
            
          
        

          
            6
            print(count)

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

📌다른 방법

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

          
            
          
            1
            # 메모리 초과
          
        

          
            2
            # 
          
        

          
            3
            # ~~~ 에라토스태네스의 채 코드 ~~~
          
        

          
            4
            
          
        

          
            5
            
          
        

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

          
            7
            
          
        

          
            8
            count = 0
          
        

          
            9
            for i in arr:
          
        

          
            10
                for j in range(2, len(arr)):
          
        

          
            11
                    if i ** j > n:
          
        

          
            12
                        break
          
        

          
            13
                    else:
          
        

          
            14
                        count += 1
          
        

          
            15
            
          
        

          
            16
            print(count)

primeList[i]가 True인 수(소수)를 따로 뽑아서 arr에 저장, arr를 탐색하며 수를 제곱하여 거의 소수를 판별하는 방식이다. 결과는 잘 나오지만 메모리 초과 오류가 발생한다.

사실 에라토스테네스의 채에는 한가지 단점이 존재하는데 메모리 소모값이 높다는 점이다. 에라토스태네스의 채 자체가 메모리를 일정부분 잡아먹기 때문에 문제 해결과정에서 메모리를 많이 할당하게 되면 메모리 초과 오류가 발생한다.

참고문서

https://wikidocs.net/21638 ( 에라토스태네스의 채 관련 자료 )

# python

# algorithm

# 백준

# 소수

# 수학

💡 로그인 하지 않아도 댓글을 등록할 수 있습니다!

👨‍💻 관련 포스트

[python]백준_1256 : 사전

백준 1256 : 사전. 해당 문제는 같은 자료를 반복해서 참고해야 하기 때문에 dp(dynamic programming)를 이용해 시간복잡도를 줄여 문제를 해결할 수 있다.

2023-03-21

[python] snscrape를 이용한 웹크롤링 및 데이터 시각화

python 모듈인 snscrape, wordCloud 모듈을 이용해 twitter에서 특정 키워드가 포함된 트윗을 크롤링하여 언급 빈도수에 따라 시각화된 자료를 생성할 수 있다.

2023-03-21

1	import sys, math
2	input = sys.stdin.readline
3
4	m, n = map(int, sys.stdin.readline().split())
5
6	primeList = [True] * (int(n ** 0.5) + 1)
7	primeList[1] = False
8
9	for i in range(2, int(n ** 0.5) + 1):
10	if primeList[i]:
11	if i * i > int(n ** 0.5):
12	break
13	for j in range(i2, int(n 0.5) + 1, i):
14	primeList[j] = False
15
16	count = 0
17	for i in range(1, len(primeList)):
18	if primeList[i]:
19	res = i * i
20	while True:
21	if res < m:
22	res *= i
23	continue
24	if res > n:
25	break
26	res *= i
27	count += 1
28
29	print(count)

1	# 메모리 초과
2	#
3	# ~~~ 에라토스태네스의 채 코드 ~~~
4
5
6	arr = [i for i in range(2, n + 1) if primeList[i] == True]
7
8	count = 0
9	for i in arr:
10	for j in range(2, len(arr)):
11	if i ** j > n:
12	break
13	else:
14	count += 1
15
16	print(count)