[C/C++] 프로젝트 오일러 #47 : 서로 다른 소인수

프로젝트 오일러 #47 문제는 소인수 분해를 하기만 하면, 어렵지 않게 풀 수 있습니다.

난이도는 5%입니다.

 

Prime factors

 

---

 

Project Euler 47번 문제는 서로 다른 소인수를 가지는 연속된 자연수를 찾는 문제입니다. 이 문제의 핵심은 연속된 네 개의 자연수가 각각 네 개의 서로 다른 소인수를 가져야 한다는 점입니다. 이러한 조건을 만족하는 가장 작은 자연수를 찾는 것이 목표입니다.

자연수는 소인수 분해를 통해 어떤 소수들의 곱으로 이루어져 있는지를 확인할 수 있습니다. 예를 들어, 14는 2와 7로 이루어져 있으며, 15는 3과 5로 이루어져 있습니다. 이러한 방식으로 각 숫자의 소인수를 분석하면서 연속된 숫자들이 일정 개수의 서로 다른 소인수를 가지는지를 검사하면 해결할 수 있습니다.

예를 들어, 만약 문제에서 연속된 세 개의 숫자가 각각 세 개의 서로 다른 소인수를 가져야 한다는 조건이 주어졌다면, 다음과 같은 숫자가 해당될 수 있습니다.
• 644 = 2 × 7 × 23 (세 개의 서로 다른 소인수)
• 645 = 3 × 5 × 43 (세 개의 서로 다른 소인수)
• 646 = 2 × 17 × 19 (세 개의 서로 다른 소인수)

위와 같이 644, 645, 646은 연속된 숫자이며, 각각 세 개의 서로 다른 소인수를 가집니다. 따라서 이들은 조건을 만족합니다. 그러나 이번 문제에서는 네 개의 숫자가 각각 네 개의 서로 다른 소인수를 가져야 하므로, 좀 더 범위를 확장하여 조건을 만족하는 수를 찾아야 합니다.

 

그동안 소인수분해는 많이 해왔지만, 이와 같은 문제는 미리 소수를 찾아내는 것이 편합니다.  범위가 지정되어 있지 않으므로, 충분히 큰 수까지 찾을 수도 있지만, 문제를 풀면서, 소인수분해한 결과가 소수이면, 소수 리스트에 저장하는 방법도 있을 수 있습니다.

 

제 경우에는 소수 리스트를 관리하지 않고, 작은 수부터 인수를 찾는 방식으로 했습니다.

---

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #47 - Distinct Primes Factors
//        - by Aubrey Choi
//        - created at 2015-03-27
//------------------------------------------------
#include <stdio.h>

bool GetPFactor(int p, int r);
int main()
{
    int count = 0;

    for( int i = 644 ; ; i++ )
    {
        if( GetPFactor( i, 4 ) == false ) { count = 0; continue; }
        if( ++count == 4 )
        {
            printf("%d\n", i-3);
            break;
        }
    }
}

bool GetPFactor(int p, int r)
{
    int t = 0;
    if( p%2 == 0 )
    {
        do { p/=2; } while( p%2 == 0 );
        t++;
    }

    for( int i = 3 ; t < r && p > 1 ; i += 2 )
    {
        if( p%i ) continue;
        do p/=i; while( p%i == 0 );
        t++;
    }
    return ( p == 1 && t == r );
}