이쁜왕자 만쉐~~

Prime ring 문제라는게 있다.. http://coding-quiz.blogspot.com/2008/08/prime-ring-problem.html n 개의 빈칸이 원형으로 배치되어 있는데, 여기에 1 ~ n 의 수를 넣어서, 접해 있는 2개의 수의 합이 소수(prime number)가 되도록 배치하라는 문제이다.. 이런 문제는 필연적으로 순열 ( permutation ) 문제가 된다.. 1~n 까지 나열할 수 있는 모든 경우를 다 돌면서 조건을 만족하는지 검색해야 한다.. 문제는 순열이다.. 1 ~ n 의 자연수로 나타낼 수 있는 모든 순열을 다 출력하는 것만으로도 조금 골치 아프다.. 조금이라도 정신이 제대로 박혀 있는 사람이라면 for 문을 n 개 돌려 가며 일일이 체크하는 삽질은 하지 않아야..

a^2 + b^2 = c^2 을 만족하는 3개의 자연수쌍을 피타고라스 수라고 합니다. (3,4,5)가 대표적이겠지요. 그리고, 이것이 서로소일때 원시 피타고라스 수라고 합니다. (3,4,5)는 원시 피타고라수 수 이지만, (6,8,10)은 아니죠. 어떤 수 n 은 여러 피타고라수 수에 속하기도 합니다. 여기서는 n 이 c 에 해당하는 경우(가장 큰 원소인경우)만 고려합니다. 예를 들어 n = 65 인경우는, 다음과 같이 4가지 방법으로 표현됩니다. 16^2 + 63^2 = 65^2 33^2 + 56^2 = 65^2 39^2 + 52^2 = 65^2 25^2 + 60^2 = 65^2 이중 (16,63,65), (33,56,65) 은 원시 피타고라스 수이고, (39,52,65) (25,60,65) 는 원시 ..