안녕하세요! 오늘은 파이썬을 배워가면서 코딩테스트 문제를 해결하는 방법에 대해 깊이 있게 다뤄보겠습니다. 특히 신기한 소수에 대해서 이야기해 보려고 합니다. 우리는 신기한 소수를 찾기 위해 어떤 접근 방식을 취해야 할지 알아보도록 하겠습니다.
문제 설명
신기한 소수란 ‘소수’ 속성을 가지면서 특정한 패턴이나 조건을 만족하는 숫자를 뜻합니다. 예를 들어, 2, 3, 5, 7과 같은 일반적인 소수뿐만 아니라, 우리가 심층적으로 다룰 신기한 소수는 다음과 같은 조건을 만족해야 합니다:
- 2와 3을 제외한 모든 소수는 6n ± 1의 형태로 표현될 수 있다.
- 각 자릿수를 더했을 때, 그 결과가 소수여야 한다.
문제: 주어진 범위 내의 신기한 소수 찾기
주어진 입력값 N까지의 모든 신기한 소수를 찾아주세요. 소수의 정의를 다시 한번 확인하고, 주어진 조건을 만족하는 소수를 찾아야 합니다.
입력
자연수 N (2 ≤ N ≤ 10,000)
출력
주어진 범위 내의 신기한 소수를 한 줄에 하나씩 출력합니다.
예제 입력
30
예제 출력
2
3
5
7
11
13
17
19
23
29
문제 해결 과정
이 문제를 해결하기 위해 먼저 기본적인 소수 판별 알고리즘을 이해해야 합니다. 소수를 찾기 위한 전통적인 방법은 에라토스테네스의 체(Sieve of Eratosthenes)입니다.
1. 소수 판별: 에라토스테네스의 체
소수를 구하기 위해서는 우리가 먼저 2에서 N까지의 모든 숫자를 담은 리스트를 만들어야 합니다. 그리고 그 리스트에서 배수의 값을 삭제해 가며 소수만 남기는 방법입니다. 이 방법은 시간적으로 효율적이며, 구현도 간단합니다.
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False # 0과 1은 소수가 아님
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
2. 신기한 소수 조건 체크
위의 함수를 통해 구해진 소수 리스트에서, 신기한 소수의 조건을 확인해야 합니다. 각 소수의 자릿수를 더해서 그 결과가 소수인지 체크하는 과정이 추가로 필요합니다.
def sum_of_digits(num):
return sum(int(d) for d in str(num))
def is_special_prime(prime_list):
special_primes = []
for prime in prime_list:
if prime > 3: # 2와 3은 신기한 소수로 별도로 처리할 수 있음
digits_sum = sum_of_digits(prime)
if digits_sum in prime_list: # 자릿수 합이 소수인지 체크
special_primes.append(prime)
return special_primes
def find_special_primes(N):
primes = sieve_of_eratosthenes(N)
special_primes = is_special_prime(primes)
return special_primes
전체 구현 코드
이제 위의 부분들을 합쳐서, 전체 프로그램 코드를 만들어 보겠습니다. 이를 통해 주어진 N값에 대해, 신기한 소수를 제대로 찾을 수 있는지를 확인할 수 있습니다.
def main(N):
primes = sieve_of_eratosthenes(N)
special_primes = is_special_prime(primes)
for prime in special_primes:
print(prime)
if __name__ == "__main__":
N = int(input("N을 입력하세요: "))
main(N)
결론
오늘은 파이썬으로 신기한 소수를 찾는 문제를 해결해 보았습니다. 이 과정을 통해 기본적인 소수 판별 방법인 에라토스테네스의 체에 대해 다시 한 번 복습하고, 자릿수 합이 소수인지 확인하는 방법까지 알아보았습니다.
이러한 알고리즘 문제들은 실전 코딩테스트에서 상당히 중요하게 다뤄지므로, 자주 연습하고 이해하는 것이 필요합니다. 다양한 문제를 통해 확장을 해보세요! 여러분의 코딩 실력이 한 단계 더 성장할 것입니다.