하루코딩 - project euler 35

안녕하세요, 이번 포스팅에서 오일러 프로젝트 35번 문항을 함께 풀어보도록 하겠습니다.
이 문항을 풀기 위해서는 파이썬에서의 string 객체의 성질을 활용하면 쉽게 해결할 수 있습니다.
뿐만 아니라 가장 기본적인 제어문인 반복문, 조건문에 대해서도 간략하게 알아보겠습니다.

 

문제 상황 파악

먼저 문제를 함께 읽어보도록 하죠. 

 

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

 

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

 

How many circular primes are there below one million?

 

즉, 197과 같이 그 rotation들 모두가 소수인 소수에 관심을 갖고 있습니다. 이러한 소수들 중 1000,000을 넘지 않는 것들의 개수를 구하면 되겠습니다.

 

어떠한 문법이 필요할까요?

먼저 1000,000까지의 수들을 각각 따져봐야 하기 때문에 자연스럽게 반복문이 필요할 것입니다.
그 중에서도 정확한 반복의 범위를 explicit하게 알기 때무에 , for 반복문을 사용하는 것이 일반적으로 효과적입니다.

또한, 위에서 언급한 성질을 만족하는 것들의 개수만 세어나갈 것이기 때문에, 반복문안에 조건문이 필요하겠죠. 

 

즉, 반복문 또 조건문, 크게 2개의 기본적인 문법만 알면 해결할 수 있는 문제가 되겠습니다.

STEP1 -  조건문 구현하기(abstract)

 

반복문은 나중으로 미뤄두고 조건문부터 함께 살펴봅시다. 조건문, 결국 어떠한 boolean 값이 True일 경우에만 그 안에 포함된 명령어들을 수행하겠다는 것이죠. 그 조건은 위에서 말했던, 가능한 모든 rotation이 소수이면 된다는 것입니다.

 

이를 위해서는

1. 각 숫자들의 가능한 모든 rotation을 구하는 명령어 뭉치와,
2. 각 숫자들이 소수인지를 판별하는 명령어 뭉치가 필요합니다.

 

같은 기능을 반복적으로 수행하는데 이를 하나의 명령어로 포장할 수 있다면 코드를 작성할 때 유지 및 보수가 편하겠죠? 이러한 것은 모든 프로그래밍 언어에서의 함수 문법으로 쉽게 가능합니다.

 

따라서 우리는 위의 2가지 목표를 달성하기 위해서 두 가지 함수를 각각 구현할 것입니다.

 

STEP2 - 소수인지 판별하는 함수 구현하기.

소수란, 1과 자기 자신만을 약수로 갖는 1이 아닌 자연수를 일컫습니다.
또한, 자연수 n = a*b로  표현이 될 때, 항상 a < sqrt(2) < b 의 부등식이 성립합니다.

그리고 우리는 n을 나누는 1과 자기 자신이 아닌 자연수 a가 존재하는지만 확인하면 된다는 것을 상기해봅시다.

그렇다면 우리는 반복할 loop의 수를 n에서 sqrt(n)로 효과적으로 좁혀놓았습니다.

 

어떤 자연수 n을 입력받았을 때, 그 자연수가 소수인지 아닌지를 boolean값을 반환하는 함수 isPrime(n)은 아래와 같이 구현할 수 있습니다.

 

from math import sqrt
def isPrime(n):
    if n<=1: return False
    N = int(sqrt(n))
    for i in range(2, N+1):
        if n % i == 0: return False
    return True

 

STEP3 - rotation(들)을 만들어 각각이 소수인지 확인하는 함수의 구현

이 문제는 애초에 주어진 수가 우선 소수이어야 그 소수들"도" 소수인지 확인하는 문제임을 명심하십시오. 즉,
소수도 아닌 수를 붙잡고 rotation을 하나하나 다 만드는 것은 효율적인 문제해결의 전략이 아니라는 것입니다.
소수인지의 여부는 STEP2의 isPrime함수를 통해 쉽게 구할 수 있습니다.

 

우리가 확인해야하는 것은 결국 가능한 모든 rotation에 대해서 그 rotation이 소수인지를 확인하면 됩니다.

이 rotation은 원래의 자료형인 int형으로는 만들기가 쉽지 않습니다. 이렇게 "가지고 있는 item의 종류는 변하지 않으면서 동시에 위치를 바꿀 때"에는 string형으로 변환한 후에 수행하는 것이 훨씬 쉽습니다.

 

문제에서 주어진 예시 197을 생각해봅시다. rotation이라 함은 결국 그 수의 가장 높은 자리수였던 1을 가장 뒤로 붙이는 것인 971, 또 971의 가장 높은 자리수였던 9를 그 맨 뒤로 붙인 719 이렇게 197을 포함하여
3개의 수만 살펴보면 되는 것입니다. 이러한 확인은 아래와 같이 쉽게 진행할 수 있습니다.

 

num = 197
num_to_string = str(num)
len_num = len(num_to_string)
curr_num = num_to_string ##curr_num은 아래의 for문에서 각 loop에서의 rotation을 저장하는 변수입니다.
for _ in range(len_num):
	if not isPrime(int(curr_num)): break ##loop에서 

	temp = curr_num[0] ## 가장 높은자리수의 숫자를 문자열 형식으로 temp 변수에 임시로 저장합니다.
    curr_num = curr_num[1:] ## 9,10 : 가장 높은자리수의 숫자를 제외한 값을 curr_num에 저장합니다.
    curr_num += temp ## 위와같이 slicing이 된 curr_num의 값에 임시로 저장한 "원래" 가장 높은 자리 수였던 값을 뒤에 이어붙입니다.(concatentate)

       

 

이를 197이 아닌 일반적인 수들에 대해서 진행을 하면 아래와 같이 확인할 수 있습니다.

def circular(num):
    if not isPrime(num): return False ## 소수가 아닌 수가 주어졌을 때에는 아래의 반복문을 실행하는 것은 불필요하므로 바로 False값을 반환하고 함수를 종료합니다
    

    num_to_string = str(num)
    len_num = len(num_to_string)
    curr_num = num_to_string
    for _ in range(len_num):
        if not isPrime(int(curr_num)): return False

        temp = curr_num[0]
        curr_num = curr_num[1:]
        curr_num += temp
    return True

 

 코드 실행 및 정답 확인

import time
from math import sqrt

start = time.time()

def isPrime(n):
    if n<=1: return False
    N = int(sqrt(n))
    for i in range(2, N+1):
        if n % i == 0: return False
    return True

def circular(num):
    if not isPrime(num): return False

    num_to_string = str(num)
    len_num = len(num_to_string)
    curr_num = num_to_string
    for _ in range(len_num):
        if not isPrime(int(curr_num)): return False

        temp = curr_num[0]
        curr_num = curr_num[1:]
        curr_num += temp
    return True


if __name__=='__main__':
    count = 0
    data = []
    for loop in range(1000000):
        if circular(loop):
            count += 1
            data.append(loop)
    print(count, time.time()-start)

    print(count)

 

---

이번 포스팅에서는 project euler 35번 문항을 함께 풀어보았습니다.

그 과정에서 string객체의 활용과 슬라이싱, 기본적인 문법인 반복문, 조건문, 함수에 대해서 알아보았습니다.
또한 문제를 해결할 때에 보다 시간복잡도에 신경쓰기 위해 불필요한 명령어의 수행을 피하는 몇 가지 방법을 살펴보았습니다.

다음 포스팅에서는 보다 더 유익한 정보로 돌아오도록 하겠습니다. 감사합니다.

 

 

---

함께 보면 좋은 글들:

[1] : 연결리스트의 ADT 및 구현

연결 리스트 ADT

[2] : 스택(stack)의 ADT