Q10622: Perfect Pth Powers

/*
    prime factorization

    Run time: 0.000
*/
#include <stdio.h>
const int N = 46350;
const int NUM = 4793;

bool isprime[N+1];
int prime[NUM];

void findPrime();
int calculate(int n);
int select(int *arr, int index);
int abs(int n);

int main()
{
    findPrime();

    int n;
    int p;
    while (scanf("%d", &n) && n)
    {
        if (n == -2147483648)
        {
           printf("31\n");
           continue;
        }

        p = calculate(n);
        printf("%d\n", p);
    }

}

void findPrime()
{
    int i, j;

    for ( i = 2; i*i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j += i)
                isprime[j] = true;

    for ( i = 2, j = 0; i <= N; i++)
        if (!isprime[i])
            prime[j++] = i;
}

int calculate(int n)
{
    int arr[NUM] = {0};
    int i, j;
    int m;
    int tmp;
    int index;
    int min;

    tmp = m = abs(n);

    for ( i = 0; (i < NUM) && (prime[i]*prime[i] <= tmp) && (m != 1); i++)
    {
        while (!(m%prime[i]))
        {
            m /= prime[i];
            arr[i]++;
        }
    }

    index = i;

    // select a suitable num in *arr
    min = select(arr, index);

    // if fail in divide
    if (min == -1)
        return 1;

    // find min
    for ( i = 1; i < index; i++)
        if (arr[i] && arr[i] < min)
            min = arr[i];

    // if divided with remainder
    for ( i = 0; i < index; i++)
        if (arr[i]%min)
            return 1;

    // if n >= 0, then p can be either odd or even
    if (n > 0)
        return min;
    // if n < 0, then p must be odd
    else
    {
        while (!(min%2))
            min /= 2;
        return min;
    }

}

int select(int *arr, int index)
{
    int i;
    for ( i = 0; i < index; i++)
        if (arr[i])
            return arr[i];
    return -1;
}

int abs(int n)
{
    return n >= 0 ? n : -n;
}