[C/C++] 프로젝트 오일러 #87 Prime Power Triples(단순 반복)

이 문제는 난이도 20%로 측정된 것입니다.

단순하게 소수를 구하고 세개의 수를 제곱, 세제곱, 네제곱한 결과가 어떤 수가 나오는지 계산하는 것입니다.

단순 작업만으로도 해결이 되는 문제죠.

 

power, cube, forth power

 

이 코드는 프로젝트 오일러 문제 #87 “Prime Power Triples”를 해결하기 위해 작성된 프로그램입니다. 이 문제의 목표는 50,000,000 미만의 숫자 중에서 \(p_1^2 + p_2^3 + p_3^4\)  형식을 만족하는 서로 다른 수의 개수를 찾는 것입니다. 여기서 \(p_1\), \(p_2\), \(p_3\)는 모두 소수입니다. 아래는 코드의 주요 부분에 대한 설명입니다.

코드 분석

1. 상수 및 배열 정의:

#define LIMIT 50000000  
static int primes\[1000000\], pcount = 0, count = 0;  
static char psummask\[LIMIT\];

• LIMIT는 50,000,000으로 설정되어 있으며, 이 값은 목표 숫자의 상한선입니다.
• primes 배열은 소수를 저장하기 위한 배열입니다.
• pcount는 찾은 소수의 개수를 나타내는 변수입니다.
• count는 조건을 만족하는 숫자의 개수를 추적합니다.
• psummask는 각 숫자가 이미 확인되었는지 표시하기 위한 배열입니다. (배열의 크기가 LIMIT이므로 50,000,000개의 원소를 가짐)

2. 소수 찾기:

primes\[pcount++\] = 2;  
for( int p = 3 ; p_p < LIMIT ; p += 2 )  
{  
    bool isPrime = true;  
    for( int i = 0 ; primes\[i\]_primes\[i\] <= p ; i++ )  
        if( p%primes\[i\] == 0 ) { isPrime = false; break; }  
    if( isPrime ) primes\[pcount++\] = p;  
}

• 이 부분에서는 소수를 찾기 위해 간단한 방법을 사용합니다. 먼저 2를 소수로 추가하고, 이후 홀수에 대해서 소수인지 판별합니다.
• p*p < LIMIT 조건은 소수를 저장할 때, 제곱근을 기준으로 하여 불필요한 계산을 줄이기 위한 것입니다.

3.  형태의 숫자 계산:

for( int i = 0 ; i < pcount ; i++ )  
{  
    int psum1 = primes\[i\]\_primes\[i\]\_primes\[i\]\_primes\[i\];  
    if( psum1 >= LIMIT ) break;  
    for( int j = 0 ; j < pcount ; j++ )  
    {  
        int psum2 = psum1 + primes\[j\]\_primes\[j\]\_primes\[j\];  
        if( psum2 >= LIMIT ) break;  
        for( int k = 0 ; k < pcount ; k++ )  
        {  
            int psum3 = psum2 + primes\[k\]\_primes\[k\];  
            if( psum3 >= LIMIT ) break;  
            if( psummask\[psum3\] == 0 ) { count++; psummask\[psum3\] = 1; }  
        }  
    }  
}

• 세 개의 중첩 루프를 사용하여 \(p_1\), \(p_2\), \(p_3\)의 조합을 만듭니다.
• psum1, psum2, psum3는 각 단계에서 계산된 합을 나타내며, LIMIT을 넘는 경우 루프를 종료합니다.
• 이미 확인한 숫자는 psummask 배열에 기록하여 중복된 숫자를 피합니다. 이렇게 하면 count가 서로 다른 숫자의 개수를 정확히 셀 수 있습니다.

4. 결과 출력:

printf("Ans = %d\\n", count);

• 조건을 만족하는 숫자의 개수를 출력합니다.

5. 실행 시간 측정:

clock_t t;  
t = clock();  
solve1();  
printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);

• clock() 함수를 사용해 코드의 실행 시간을 측정하고, 완료 후 시간을 출력합니다.

요약

이 코드는 50,000,000 미만의 숫자 중에서  형태를 만족하는 숫자의 개수를 찾습니다. 세 개의 중첩 루프를 통해 가능한 모든 조합을 계산하고, 배열을 사용하여 중복을 피하는 방식으로 문제를 해결합니다. 코드의 효율성은 특히 소수를 찾는 방식과 각 루프의 종료 조건 덕분에 개선됩니다.

 

작성한 코드는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #87 - Prime Power Triples
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    LIMIT    50000000

void solve1()
{
    static int primes[1000000], pcount = 0, count = 0;
    static char psummask[LIMIT];

    primes[pcount++] = 2;
    for( int p = 3 ; p*p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 0 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) primes[pcount++] = p;
    }

    for( int i = 0 ; i < pcount ; i++ )
    {
        int psum1 = primes[i]*primes[i]*primes[i]*primes[i];
        if( psum1 >= LIMIT ) break;
        for( int j = 0 ; j < pcount ; j++ )
        {
            int psum2 = psum1 + primes[j]*primes[j]*primes[j];
            if( psum2 >= LIMIT ) break;
            for( int k = 0 ; k < pcount ; k++ )
            {
                int psum3 = psum2 + primes[k]*primes[k];
                if( psum3 >= LIMIT ) break;
//                printf("%d = %d^2 + %d^3 + %d^4\n", psum3, primes[k], primes[j], primes[i]);
                if( psummask[psum3] == 0 ) { count++; psummask[psum3] = 1; }
            }
        }
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}