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

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

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

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

3.8초 정도가 걸렸다.

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

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

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

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

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

+

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

아래는 먼저 짠 수도 코드