코딩 연습

프로젝트 오일러 51번 본문

project euler with python

프로젝트 오일러 51번

코딩아저씨 2016. 3. 15. 15:30
반응형

얼마전에 project euler 라는 사이트를 알게 되었고, 프로그래밍 연습도 할 겸 해서 한 문제씩 풀고 있다. 재미있게 여러 가지 연습을 해 볼 수 있어서 좋다고 생각한다. 대부분의 문제가 간단하게 풀리지만 어떤 경우는 오랜 시간 생각을 많이 해야만 풀리는 문제도 있는데, 51번 문제가 그러했다. 프로젝트 오일러 사이트에서 다른 사람들을 위해서 정답을 공개하지는 말라는 당부가 있었기에 여기서는 문제를 풀기 위한 힌트를 제공하려고 한다.


51번 문제는 다음과 같다.



By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.


예를 통해서 문제를 설명하는게 편할것 같다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위 숫자들은 첫 번째 , 두 번째, 다섯 번째 자리가 각각 5, 6, 3으로 고정되어 있고, 세 번째, 네 번째 자리가 같은 숫자들로 이루어진 소수들이다. (56223, 56553, 56883 은 소수가 아니다) 즉, 세 번째 네 번째 자리가 0~9로 채워질 때, 소수가 되는 것이 7개가 되는 경우이다. 

이와 같이 일정 부분이 특정한 숫자로 고정되어 있고, 나머지 부분들은 0~9까지 같은 숫자들로 이루어져 있는 소수들을 8개 찾으려고 한다. 8개 소수 들 중 가장 작은 수를 찾아라. (위의 예에서 7개의 소수는 조건을 만족시키면서 7개의 소수를 만들 때 가장 작은 수들이고, 그 중 최솟값은 56003이 된다)



처음에는 이 문제가 그냥 무식하게 접근하여 하나씩 체크하면 되는 문제인지 알았다. 그러나 그렇게 접근하였더니 밤새도록 컴퓨터를 돌려도 결과가 나오지 않는 것이었다. 뭔가 다른 방법이 없을까 나름 오랫동안 고민을 하여 몇 가지 힌트가 될만한 단서들을 찾아내었고, 그걸 통해서 이 문제를 풀 수 있었다.


1. 0부터 9까지의 수가 반복되는 자리의 개수는 \(3, \; 6, \; 9, \; \cdots \) 즉 3의 배수가 된다.



2. 마지막 자리(1의 자리)는 반드시 고정된 숫자가 오는 자리이다.



이 두 가지 힌트를 가지고 문제를 접근하게 되면 좀 더 빠르게 문제를 해결할 수 있을 것이다.

먼저 고정되지 않고 반복되는 자리가 어디인지 결정하고 그 자리의 숫자들이 각각 0에서 9인 수들을 다 걸러낸다.

걸러낸 수들에서 나머지 고정된 자리의 숫자들이 같은 것끼리 모아 그 숫자가 8개 이상이 되는 것 중 가장 작은 수가 이 문제의 정답이다.

물론 각각의 숫자가 소수인지는 체크해야만 한다.


반응형

'project euler with python' 카테고리의 다른 글

프로젝트 오일러 68번  (0) 2016.03.15
프로젝트 오일러 67번  (0) 2016.03.15
프로젝트 오일러 66번  (0) 2016.03.15
프로젝트 오일러 59번  (0) 2016.03.15
프로젝트 오일러 54번  (0) 2016.03.15


Comments