37. 프로젝트 오일러 : 잘라도 소수가 되는 소수
난이도는 5%로 낮은 난이도의 문제입니다. 이 문제는 앞을 잘라도 소수가 되는 소수를 찾아야 합니다. 예를 들면 3797은 자체로 소수이지만, 797, 97, 7 도 소수이며, 반대로 379, 37, 3도 소수가 됩니다. 원래라면, 모든 소수를 다 찾고, 모든 소수에 대해서 잘라가면서 소수인지 검사하면 되는 간단한 프로그램이 됩니다. 소수를 검사하기 위해서 소수를 다 찾고, 이진 검색을 이용해서 소수인지 검사하면 편하지만, 제가 중점을 둔 것은 이러한 소수의 성질이었습니다. 두자릿수 이상의 수중, 마지막 자리가 5라면 그 수는 반드시 5로 나누어지기 때문에 소수가 될 수 없습니다. 또한 첫 숫자가 9이거나 마지막 숫자가 9라면, 잘라내기에 의해서 9가 남기때문에 첫 숫자와 마지막 숫자는 9가 될 수 없습..
2015. 4. 18.