The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
2개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 2개의 숫자는 다음과 같다:
14 = 2 × 7
15 = 3 × 5
3개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 3개의 숫자는 다음과 같다:
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
4개의 서로 다른 소수를 인자로 가지는, 처음으로 연속되는 3개의 숫자를 구하시오. 이 중 첫 숫자는 무엇인가?
--------------------------------------------------------------------------
5번 문제를 풀 때 소인수분해를 구현할 만큼 파이썬을 이해한 것이 아니어서 우회하는 방법으로 해결했는데, 이 문제에서는 소인수분해를 이용해서 해결했다.
해당하는 숫자보다 작은 값을 가지는 소수 리스트를 만들어 나가면서, 해당 숫자를 소수 리스트의 값으로 차례대로 계속 나눠 몇 개의 소수로 구성되는지를 판별하는 것이다. 예를 들어, 45는 2로 나눠지지 않고, 3으로는 2번 나눠지고(45/3=15, 15/3=5), 5는 5로 1번 나눠지므로 소인수는 3,5인 2개로 판별한다.
문제에서 요구하는 대로 소인수분해를 단순하게 구현한 덕분에 답을 구하는 데 시간이 많이 소요되었다. 아무래도 이 문제에서 요구하는 것은 문제에 충실하게 답을 구하는 것 보다는, 좀 더 효율적으로 답을 구하는 방법을 생각해 보는 것일 수도 있겠다.