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의 자릿수를 바꿔 만들어지는 197, 971, 719 모두가 소수이기 때문에 순환소수(circular prime)이라 불린다.
100 이하의 수에는 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97의 13개 순환소수가 있다.
백만 이하의 수에는 몇 개의 순환소수가 있는가?
--------------------------------------------------------------------------
순환소수라 불렀지만 수학 용어는 아니고 임의로 붙인 명칭이다. 숫자를 한 방향으로 회전시키면서 나온 숫자가 소수인지 판별하면 된다.
단순하게 생각해보면 2부터 백만까지 반복해가면서 소수인지 판별하고, 자릿수를 바꿔 만들어지는 수가 모두 소수인지 판별하는 방법이 있다. 하지만, 소수인지 판별하는 것이 상대적으로 시간이 많이 소요되는 과정이기 때문에 성능이 나쁠 것 같아 다른 접근을 하기로 했다.
미리 2부터 백만까지의 소수를 리스트로 만들어 놓고, 리스트에 있는 소수를 대상으로 자릿수를 바꿔 만들어지는 수가 만들어 놓은 소수 리스트에 있는지 확인하는 방식으로 소수 여부를 판별하게 했다. 그리고, 조금 더 계산 속도를 빠르게 만드는 방법으로는 소수인 숫자 어딘가에 짝수나 5의 배수가 있으면 순환하는 중 1의 자리에 오게 되면 소수가 아니게 되기 때문에(2의 배수 or 5의 배수), 각 자릿수 중에 0,2,4,6,8과 5가 있으면 소수가 아닌 것으로 보고 다음 숫자로 넘어가게 할 수 있다.