네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 7109와 1097 또한 소수입니다.
3, 7, 109, 673는 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다,
다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서, 그 합의 최소값을 구하세요.
드디어 60번문제..
처음에는 5개 소수 리스트를 하나씩 뽑아내서 순열 조합을 생성하고 (5C2)
이 조합들이 모두 소수인지 확인하는 형태로 구현했는데 2시간이 넘어도 답이 안나와 -_-;
그래서 앞쪽부터 보초를 많이 세우는 방식으로....
Python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def isPrime(n): | |
| n = abs(int(n)) | |
| if n < 2: | |
| return False | |
| if n == 2: | |
| return True | |
| if not n & 1: | |
| return False | |
| for x in range(3, int(n**0.5)+1, 2): | |
| if n % x == 0: | |
| return False | |
| return True | |
| max = 10000 | |
| min = 1 | |
| prime_list = [str(n) for n in range(min, max) if isPrime(n)] | |
| def allPrime(iterable): | |
| for element in iterable: | |
| if not isPrime(int(element)): | |
| return False | |
| return True | |
| print (prime_list) | |
| for p1 in range(0, len(prime_list)-4): | |
| for p2 in range(p1+1, len(prime_list)-3): | |
| if not isPrime(prime_list[p1] + prime_list[p2]) or not isPrime(prime_list[p2] + prime_list[p1]): | |
| continue | |
| for p3 in range(p2+1, len(prime_list)-2): | |
| if not isPrime(prime_list[p1] + prime_list[p3]) or not isPrime(prime_list[p3] + prime_list[p1]) or not isPrime(prime_list[p2] + prime_list[p3]) or not isPrime(prime_list[p3] + prime_list[p2]): | |
| continue | |
| for p4 in range(p3+1, len(prime_list)-1): | |
| if not isPrime(prime_list[p1] + prime_list[p4]) or not isPrime(prime_list[p4] + prime_list[p1]) or not isPrime(prime_list[p2] + prime_list[p4]) or not isPrime(prime_list[p4] + prime_list[p2]) or not isPrime(prime_list[p3] + prime_list[p4]) or not isPrime(prime_list[p4] + prime_list[p3]): | |
| continue | |
| for p5 in range(p4+1, len(prime_list)): | |
| if not isPrime(prime_list[p1] + prime_list[p5]) or not isPrime(prime_list[p5] + prime_list[p1]) or not isPrime(prime_list[p2] + prime_list[p5]) or not isPrime(prime_list[p5] + prime_list[p2]) or not isPrime(prime_list[p3] + prime_list[p5]) or not isPrime(prime_list[p5] + prime_list[p3]) or not isPrime(prime_list[p4] + prime_list[p5]) or not isPrime(prime_list[p5] + prime_list[p4]): | |
| continue | |
| print (prime_list[p1], prime_list[p2], prime_list[p3], prime_list[p4], prime_list[p5], int(prime_list[p1])+int(prime_list[p2])+int(prime_list[p3])+int(prime_list[p4])+int(prime_list[p5])) |
보통 오일러프로젝트 풀면서 전체를 먼저 구해놓고 거기서 뽑아내는게 빨랐기 때문에
그 방법을 먼저 썼는데.. 그것도 case by case였네요.. 특히 brute force 방식에서는
보초를 많이 세워서 걸러주는게 가장 좋은 방법인듯 합니다..
그놈의 LOL과 디아 때문에 너무 텀이 길었네요 --;;;