함수 1

* 틀린 내용이 있을 시 지적 부탁드립니다.

문제는 더블릿 8 함수에 있는 prime_palin입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/prime_palin/prime_palin.php?pname=prime_palin

소수이면서 앞뒤로 순서를 바꾸어도 같은 숫자를 구하는 문제입니다.

평범하게 소수를 구하고 회귀수를 구하거나 하면 시간초과 에러가 뜰겁니다.  회괴수인지 먼저 문자열 길이를 구해 앞뒤로 검사해주고 통과하면 소수인지를 확인하는 방법도 저는 시간초과가 떴습니다.

재귀를 통해서 풀었는데 범위 내의 회귀수를 하나씩 만들어가면서 만들어진 수에대해 소수검사를 하였습니다.

우선 최대값을 통해 만들어질 수 있는 자리수를 구합니다.  500이면 3자리이고 회귀수를 만들기위해 대입해야할 자리는 십의자리까지입니다.  이 수를 a라고 하겠습니다.  그 이상의 자리는 이전의 자리수를 이용해 대입하면 회귀수가 됩니다.

맨 앞자리를 0과 2가 아닌 숫자로 1~9까지 넣어줍니다.  그 후 각각의 1의 자리에 대해 자리수를 올려가면서 다시 0~9까지 수를 대입합니다.  이 과정은 a자리수까지 반복됩니다.  각각 a자리까지 완성된 수에 대해 그 윗자리 수들은 a이하의 자리수를 역으로 대입하여 만들어집니다.

완성된 수는 5~500의 수를 가져야 하는데 a자리 인덱스는 1까지 됩니다.  마지막 값인 9989899의 경우 a는 3으로 9899까지 완성되고 여기에 앞의 3자리를 이용해 9989899를 만들게 됩니다.  그런데 항상 최대값의 자리수만 이용할 수는 없으므로<마지막 최대값인 100000000의 경우 a는 5인데 완성된 수는 7의 자리(a=4), 5의 자리(a=3)가 있을 수도 있음> 임시로 a를 2부터 놓고(3의 자리) 여기서부터 올려나갑니다.

이렇게 완성된 회귀수에 대해 소수인지를 검사하고 출력하면 됩니다.