35. Circular primes

1. 개요

  문제는 이곳에서 확인할 수 있다. 197은 특이한 소수인데, 각 자리의 수를 순환시켜도 모두 소수이기 때문이다. 즉, 971, 719 모두 소수이다. 이와 같은 특성을 보이는 1,000,000 보다 작은 소수의 개수를 구하는 것이 목표이다. 단, 중복을 허용한다. 즉, 197, 971 그리고 719는 한가지 소수를 순환하여 만들 수 있지만 따로 센다.

2. 구현 ver 1.0

  먼저 100만 이하의 소수를 에라스토테네스의 체를 이용하여 구한다. 이후 각 소수를 순환시키면서 그 수가 소수인지 확인한다.

# -*- coding: utf-8 -*- 

import math as m

# 1. Find primes 
lim = 1000001
prime_candidate = list(range(2, lim))
prime_list = []

while prime_candidate[0] < m.sqrt(lim):
	prime = prime_candidate.pop(0)
	prime_list.append(prime)
	prime_candidate = list(filter(lambda x: x % prime != 0, prime_candidate))
prime_list += prime_candidate

print(len(prime_list), 'primes found...')

# Find the primes fitting the condition
answer = 0
while prime_list:
	
	prime = prime_list.pop(0)
	prime_digit = [s for s in str(prime)]
	n = 1
	
	prime_digit.append(prime_digit.pop(0))
	prime_candidate = int(''.join(prime_digit))
	
	while prime != prime_candidate:
		if not prime_candidate in prime_list or \
			any(True for d in prime_digit if d in ['2','5','4','6','8','0']):
			break
		prime_list.remove(prime_candidate)
		prime_digit.append(prime_digit.pop(0))
		prime_candidate = int(''.join(prime_digit))
		n += 1
	
	else:
		print(prime)
		answer += n

print('ANSWER: ', answer)

답은 55이다.

3. 구현 ver 2.0

  구현 ver 1.0의 코드는 답을 찾아 주지만 굉장히 오래 걸린다. 원인을 찾기 위하여 이 문제의 게시판에 들어가 남들의 코드를 관찰하였고 몇가지 개선점을 도출할 수 있었다.

(1) 숫자를 문자로 바꾼 후 slicing을 하지 않아도 숫자를 순환시킬 수 있다. 즉, 197을 순환시키기 위해서 197을 100으로 나눈 후 나머지에 10을 곱한 후 몫을 더하는 방식을 사용할 수 있다.

(2) 숫자를 순환시키는 과정에서 모든 결과를 list로 가지고 있을 필요가 없다. 한번이라도 조건에 어긋나면 이후의 숫자는 볼 필요가 없으므로 숫자를 순환시키는 부분은 yield를 사용하여 iterator로 구현하는 것이 효율적이다.

(3) list에 대한 연산은 느리기 때문에 이와 같은 문제에서는 bytearray를 사용하여 어떤 숫자가 소수인지 아닌지만 판단해도 좋다.

  이상의 개선점을 반영하여 코드를 수정하였다. 답은 55로 같고, 속도는 훨씬 개선되었다.

# -*- coding: utf-8 -*- 

import math

# 에라스토테네스의 체를 이용하여 소수를 찾는다. 
n = 1000000
is_prime_list = bytearray([1])*(n+1) 
is_prime_list[0] = is_prime_list[1] = 0

for p in range(2, int(math.sqrt(n))+1):
	if is_prime_list[p]:
		m = n//p - p + 1
		is_prime_list[p*p::p] = bytearray(m)

# 소수를 순환하여 반환한다.
def rotated_prime(prime):
	n_digit = int(math.log10(prime))
	divisor = 10**n_digit
	
	for i in range(n_digit + 1):
		q, r = divmod(prime, divisor)
		prime = r * 10 + q 
		yield prime, q not in [0, 2, 4, 5, 6, 8]

answer = 0
for number, is_prime in enumerate(is_prime_list):
	if is_prime:
		
		if all( is_prime_list[s] & is_valid for s, is_valid in rotated_prime(number)):
			answer += 1

answer += 2 # for 2, 5
print('ANSWER: ', answer)