37. 프로젝트 오일러 : 잘라도 소수가 되는 소수
난이도는 5%로 낮은 난이도의 문제입니다. 이 문제는 앞을 잘라도 소수가 되는 소수를 찾아야 합니다. 예를 들면 3797은 자체로 소수이지만, 797, 97, 7 도 소수이며, 반대로 379, 37, 3도 소수가 됩니다. 원래라면, 모든 소수를 다 찾고, 모든 소수에 대해서 잘라가면서 소수인지 검사하면 되는 간단한 프로그램이 됩니다. 소수를 검사하기 위해서 소수를 다 찾고, 이진 검색을 이용해서 소수인지 검사하면 편하지만, 제가 중점을 둔 것은 이러한 소수의 성질이었습니다. 두자릿수 이상의 수중, 마지막 자리가 5라면 그 수는 반드시 5로 나누어지기 때문에 소수가 될 수 없습니다. 또한 첫 숫자가 9이거나 마지막 숫자가 9라면, 잘라내기에 의해서 9가 남기때문에 첫 숫자와 마지막 숫자는 9가 될 수 없습..
2015. 4. 18.
34. 프로젝트 오일러 #34 : 자릿수의 팩토리얼 합
연달아서 난이도 5% 정도의 문제네요. 이번 문제는 각각의 자릿수의 팩토리얼 합이 자신이 되는 숫자를 찾는 것입니다. 예를 들어서 145란 숫자는, 가 됩니다. 이번 문제는 이와 비슷한 숫자들의 합을 구하는 것입니다. 이제 프로젝트 오일러를 이정도까지 진행하셨다면, 십진수의 자릿수를 빼는 것에는 다들 어느정도 경험이 있을 것이라 생각합니다. 제 경우에는 각 자릿수의 팩토리얼 값을 미리 저장해서 사용했습니다. 9! = 362880 이므로, 대충 6자릿수자일거라고 생각하면 됩니다. 그래서 숫자범위를 그렇게 정했습니다. 제가 작성한 프로그램은 다음과 같습니다. #include int main() { int facts[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 36280..
2015. 4. 13.
