본문 바로가기

오일러프로젝트

[오일러프로젝트] 60번문제


네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 7109와 1097 또한 소수입니다.
3, 7, 109, 673는 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다,

다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서, 그 합의 최소값을 구하세요.



드디어 60번문제..

처음에는 5개 소수 리스트를 하나씩 뽑아내서 순열 조합을 생성하고 (5C2)

이 조합들이 모두 소수인지 확인하는 형태로 구현했는데 2시간이 넘어도 답이 안나와 -_-;


그래서 앞쪽부터 보초를 많이 세우는 방식으로....




Python

보통 오일러프로젝트 풀면서 전체를 먼저 구해놓고 거기서 뽑아내는게 빨랐기 때문에

그 방법을 먼저 썼는데.. 그것도 case by case였네요.. 특히 brute force 방식에서는

보초를 많이 세워서 걸러주는게 가장 좋은 방법인듯 합니다..

그놈의 LOL과 디아 때문에 너무 텀이 길었네요 --;;;