[백준] 2023 신기한 소수 (Python)

https://www.acmicpc.net/problem/2023

문제를 풀기 앞서, 소수에 대해 알아보자!

소수(Prime Number) : 1과 자기 자신만을 약수로 갖는 수

소수 판별법

흔히 에라토스테네스의 체 알고리즘으로 소수를 판별하기도 하지만, 이번 문제에서는 사용하지 않았다.

1) 2부터 n-1까지 나누기

N이라는 숫자가 소수가 되려면 N은 range(2, N) 범위의 자연수로 나누어 떨어지면 안 된다.
예를 들어 4는 2~4 범위에서 2로 나누어 떨어지므로 소수가 아님을 알 수 있다.

1-1) 구현

N이 1 이상의 다른 수로 나눠지지 않는 소수인지 판별

• 시간복잡도: O(n) ➡️ 2부터 n-1까지의 수를 모두 확인하기 때문

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

2) n/2까지 나누기

N 자신을 제외한 N의 약수 중에서 가장 큰 약수는 N/2보다 작거나 같기 때문에 위의 판별에서 범위를 줄여 소수인지 판별할 수 있다.
예를 들어, 12의 약수 1, 2, 3, 4, 6, 12 중 12 자신을 제외한 가장 큰 약수는 6으로 12/2와 같다.

2-1) 구현

def is_prime(n):
	for i in range(2, n/2+1):
    	if n % i == 0:
        	return False
    return True

• 시간 복잡도 : O(n) ➡️ 2부터 n/2까지의 자연수만 순회하여 첫번째 방법보다는 확인할 조건이 절반이지만, 여전히 느리다.

접근 방식

📍 재귀 함수를 이용한 DFS 문제 (에라토스테네스의 체 알고리즘을 이용해 for문으로 풀이한다면 시간초과가 난다고 한다.)

1. 자릿수가 한 개인 소수 2, 3, 5, 7부터 탐색을 시작한다.
2. 자릿수가 두 개인, 현재 수 10 + a를 계산하여 소수 여부 판별, 소수라면 자릿수를 하나 늘린다.
   ➡️ 2 10 + 3과 같이 두 자리수이며 소수인 경우 자릿수를 늘려 231부터 탐색을 시작한다.
   (단, a가 짝수라면 항상 2를 약수로 가지므로 a가 짝수인 경우 제외)
3. 자릿수를 입력받은 N까지 확장하여 소수라면 해당 값 출력
   

풀이

• sys.setrecursionlimit() 메서드는 Python 인터프리터 스택의 최대 깊이를 필요한 제한으로 설정하는 데 사용된다. 이 제한은 모든 프로그램이 무한 재귀에 들어가는 것을 방지한다.
  (파이썬 인터프리터 소스 코드는 최대 재귀 깊이가 1,000으로 정의되어 있음)

  import sys
  print(sys.getrecursionlimie()) # 1000

• len()은 문자열(string)의 길이를 반환하는 함수이므로 int type인 숫자를 str type으로 변환해야 한다.

참고

• Do it! 알고리즘 코딩 테스트 - 파이썬 편
• 소수(Prime Number) 판별법
• https://www.geeksforgeeks.org/python-sys-setrecursionlimit-method/