[C/C++] Project Euler #47 - Distinct Primes Factors

The Project Euler #47 problem can be solved without much difficulty as long as prime factorization is performed correctly.  The difficulty level of this problem is 5%.

---

Project Euler #47 is a problem that involves finding consecutive natural numbers with distinct prime factors. The key aspect of this problem is that four consecutive natural numbers must each have exactly four distinct prime factors. The goal is to find the smallest natural number that meets these conditions.

 

A natural number can be factorized into the product of prime numbers. For example, 14 consists of 2 and 7, while 15 consists of 3 and 5. By analyzing the prime factors of each number, we can determine whether a sequence of consecutive numbers contains a specified number of distinct prime factors.

 

For instance, if the problem required us to find three consecutive numbers, each having exactly three distinct prime factors, the following numbers would satisfy the condition:
• 644 = 2 × 7 × 23 (three distinct prime factors)
• 645 = 3 × 5 × 43 (three distinct prime factors)
• 646 = 2 × 17 × 19 (three distinct prime factors)

 

As seen above, 644, 645, and 646 are consecutive numbers, and each of them has three distinct prime factors. Thus, they fulfill the given condition. However, in this problem, we need to find four consecutive numbers, each having exactly four distinct prime factors, which requires extending the search range.

---

Since prime factorization is commonly used, it is more convenient to precompute prime numbers in advance. Although there is no predefined range given in the problem, we can search up to a sufficiently large number. Additionally, while solving the problem, if the result of prime factorization indicates a prime number, we could store it in a prime list as an alternative approach.

 

In my case, rather than maintaining a prime list, I used an approach where I directly searched for factors starting from smaller numbers.

---

Prime Factors

Here is the source code I wrote:

//------------------------------------------------
//    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 );
}