프로젝트 오일러 #29 서로 다른 n제곱 개수

이번 문제는 중복을 처리하는 문제이기는 하지만,

숫자의 범위가 큰 까닭에, big integer를 써서 처리를 하든지, 아니면 무언가 다른 방도를 생각해서 해주어야 합니다.

 

서로 다른 n제곱 갯수를 구하기 위해서는 다음과 같은 생각을 좀 해주어야 합니다.

 

 

서로 다른, a, b (b > a) 에 대하여, \(a^m\), \(b^n\)이 갈은 수가 되기 위해서는 반드시, b는 a의 제곱승이어야 합니다.  그렇지 않다면, 같은 숫자가 나올 수가 없습니다.

 

이것을 토대로 해서 프로그램을 작성해보았습니다.

 

전반부 프로그램은 제곱수가 아닌 a 에 대하여 \(a^k\)을 모두 체크하고, 그 때의 연산 결과를 1승만 가능한 경우, 2승까지 가능한 경우, 3승까지 가능한 경우 등등으로 나누어서 그 출력값을 미리 v란 배열에 저장합니다.

 

예를 들어서 3이란 숫자를 생각한다면, 3, 9, 27, 81 의 100 이하의 제곱수가 생깁니다.  3은 4제곱까지 가능한 수가 되겠죠.  그러면, 3의 1승부터 3의 100승까지 가능하니 일단 100개의 서로 다른 n제곱수가 나오겠죠.  9의 1승부터 9의 100승까지 계산을 하는 것은 3의 2승부터 3의 100승까지 짝수승들이 빠지므로, 그 숫자가 나올겁니다.  이렇게 함으로써 우리는 3이란 숫자만 가지고, 3과 연관된 9, 27, 81이란 숫자까지 합친 서로 다른 n제곱수를 구할 수가 있습니다.

 

후반부 프로그램은 실제 a의 n제곱을 하는 것을 시뮬레이션합니다.

 

이렇게 함으로써 계산량을 많이 줄이고 big integer 연산과 중복 처리를 말끔하게 처리할 수 있습니다.

 

제가 짠 프로그램은 참고용으로 봐주세요.

 

#include <stdio.h>
#include <memory.h>

int main()
{
    int n = 100;
    int md = 1;
    while( n>>md ) md++;
    int v[100];

    char check[1000];
    memset(check, 0, sizeof(check));
    for( int i = 1, ls = 0 ; i < md ; i++ )
    {
        for( int j = 2 ; j <= n ; j++ )
            if( !check[i*j] ) { check[i*j] = 1; ls++; }
        v[i] = ls;
    }

    int sum = 0;
    memset(check, 0, sizeof(check));
    for( int a = 2 ; a <= n ; a++ )
    {
        if( check[a] ) continue;
        int c = 1;
        int t = a*a;
        for( ; t <= n ; t *= a, c++ ) check[t] = 1;
        sum += v[c];
    }

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

 

python으로 작성한 소스는 다음과 같습니다.

 

from sets import Set
set = Set([])
for a in range(2,101):
    for b in range(2,101):
    set.add(a**b)
        
print len(set)