[C/C++] 제곱

최근에 친구랑 같이 풀었던 알고리즘 문제

문제)
입력으로 자연수 a가 주어진다. 이 때, 자연수 k를 곱한 결과가 거듭제곱수가 되는 최소의 k를 구하는 프로그램을 작성하여라.

 

인풋 예제)

5 // 데이터 입력 갯수 2 // 첫번째 인풋 4 // 두번째 잇풋 12 // 세번째... 14 919451

 

 

 

코드에 수도코드도 안지워서 코드로 봐도 되지만 간단히 설명하면

1. 필요한 범위까지의 소수를 구한다.
2. 지금 값이 소수인지 확인한다.
3. 아니라면, (while) 가장 작은 소수부터 k로 나눠 본다. 
    3-1. 홀수로 나눠지면, k를 곱한다.
    3-2. 짝수로 나눠지면, 그대로 둔다.

#include <stdio.h>
 
#define MAX 10000001
 
int PRIMES[664580];
int PRIMES_SIZE;
int PRIMES_MAP[MAX];
 
#include <stdio.h>
int main(void)
{
    int test_case;
    int T;
    register int i, j;
    scanf("%d", &T);
    PRIMES_SIZE = 0;
    for (i = 2; i * i < MAX; ++i) {
        if (PRIMES_MAP[i] == 1) continue;
        PRIMES[PRIMES_SIZE++] = i;
        PRIMES_MAP[i] = 0;
        for (j = 2 * i; j < MAX; j += i) {
            PRIMES_MAP[j] = 1;
        }
    }
    for(i = 2; i < MAX; ++i) {
        if (PRIMES_MAP[i] == 0) PRIMES[PRIMES_SIZE++] = i;
    }
 
    // printf("PRIMES_SIZE: %d\n", PRIMES_SIZE);
    // for (i = 0; i < PRIMES_SIZE; ++i) {
    //     printf("%d ", PRIMES[i]);
    // }
    // for (i = 0; i < MAX; ++i) {
    //     printf("%d ", PRIMES_MAP[i]);
    //     if(i%10 == 0)printf("\n");
    // }
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int a; // input 소인수 분해 후, 제곱이 아닌 것만 필터링
        scanf("%d", &a);
        int result = 1;
        // const aPrimes: number[] = divideByPrimeNumber(a);
            // check % 2 ? aPrime.add : next
        // const result: number = getNumberToMakeSquare(aPrimes);
        int divider = 0;
        for(i = 0; PRIMES[i] <= a; ++i) {
            if(PRIMES_MAP[a] == 0) {
                result *= a;
                break;
            }
            divider = PRIMES[i];
            int check = 0;
            while(a % divider == 0) {
                a /= divider;
                check++;
            }
            if (check % 2) {
                result *= divider;
            }
        }
        printf("#%d %d\n",test_case, result);
    }
    return 0;
}