본문 바로가기
개발/알고리즘 문제

[Project Euler 35] 백만 이하인 circular prime 개수 구하기

by 유다110 2016. 4. 23.
반응형

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다.

이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다.


그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?


from itertools import permutations
from collections import deque
import primesieve
#def is_prime(num):
# result = False
# for i in range(2, num):
# if num > 2 and num % i == 0 :
# return False
# else :
# result = True
# return result
#def is_circular_prime(prime):
# result = False
# prime_str_list = list(str(prime))
# prime_deque = deque(prime_str_list)
# for i in range(len(prime_deque)):
# prime_deque.rotate()
# rotated_num = int(''.join(prime_deque))
# if is_prime(rotated_num) == True :
# result = True
# else :
# result = False
# break
# return result
def is_circular_prime(prime):
result = False
prime_str_list = list(str(prime))
prime_deque = deque(prime_str_list)
for i in range(len(prime_deque)-1): #이 부분에서 -1을 넣었더니 연산이 3.8 >> 2.4 초로 줄었다!
prime_deque.rotate()
rotated_num = int(''.join(prime_deque))
if primesieve.generate_n_primes(1, rotated_num)[0] == rotated_num:
result = True
else :
return False
return result
def get_circular_prime(range_to):
count = 0
prime_list = primesieve.generate_primes(range_to) #[2, 3, 5, 7, 11, 13, 17, 19....]
for prime in prime_list:
if is_circular_prime(prime) == True :
count += 1
return count
print(get_circular_prime(1000000))



3.8초 정도가 걸렸다.

이번 문제도 꽤나 재밌었다.

처음엔 순환이 아니라, 순열로 착각해서 itertools 모듈의 permutations 함수를 썼었다.

삽질 잠깐 하다가, deque로 만들어 그 길이만큼 rotate() 시켰다.(deque는 처음 써봤다!)


신기하게도(?) primesieve 모듈에 소수 판별 함수가 없어서, 해당 num을 기준으로 하나의 소수만을 뽑아내, num과 같은 수인지 판별하는 식으로 썼다.

처음엔 위와 같이 prime 판별 함수를 직접 만들었는데...미친듯이 느려서 바꿨다.


+

와, 어차피 1,000,000 이하의 소수만 돌리는 거니까, deque를 rotate() 할 때 본인은 제외해도 되니, range에 -1을 했더니 2.4초 정도로 줄었다!!!


아래는 먼저 짠 수도 코드

#소수구하는 모듈인 primesieve로 일단 구함. 그중에 고름
#순환소수인지 판별할 때는 순열조합 모듈인 itertools.permutations를 사용
import primesieve
def is_circular_prime(num):
for 검사해야할num in permutations(str(num)):
검사해야할num = int(''.join(검사해야할num))
if 검사해야할num == 소수:
result = True
else :
result = False
return result
def get_circular_prime(range_to):
count = 0
prime_list = generate_프라임(range_to) #[2, 3, 5, 7, 11, 13, 17, 19....]
for prime in prime_list:
if is_circular_prime(prime) == 'True':
count += 1
return count


반응형

댓글