Find the minimum power of a number N?

Question

C++ / C#

Degree
In order to check how her students can count, every year Maria Ivanovna gives them the same task at home - for a given natural A, find the minimum natural N such that N is to the power of N (N multiplied by itself N times) is divisible by A. From year to year and from student to student, only the number A changes.

You have decided to help future generations. To do this, you need to write a program that solves this problem.

Specifications Input

The input contains a single number A (1≤A≤109 — just in case; what if Maria Ivanovna asks a big number to "fill up" someone...).

Output Print

the number N.

Examples
Input
1
Output
1
Input
8
Conclusion
4

#include <iostream>
using namespace std;
int main()
{
    int a ;
    int n;
    cin >> a;
    for ( int n = 1; n <= 30; n++)
    {
        int t = a;
       int f = t;
         int n1 = n;
        for (int i = 0; i < n; i++)
        {
            while (n1 != 0 and t != 0)
            {
                if (n1 > t)
                {
                    n1 = n % t;
                }
                else
                {
                    t = t % n1;
                }
                
            }
            f = f / (n1 + t);
        }
        if (f == 1)
        {
            cout << n;
            return 0;
        }
    }
      n = 1;
    for (int p = 2; p * p <= a; p++)
    {
        if (a % p == 0)
        {
            n += p;
            while (a % p == 0)
            {
                a /= p;
            }
        }
  }

    if (a > 1)
    {
        n *= a;
}
    cout << n;
    return 0;
}
Помогите пожалуйста сайт пишет, что программа выдаёт неверный ответ

Answer 1

The solution to the problem should be:
Since n^n is divisible by a, then n is divisible by all prime divisors of a. Therefore, we need to factorize a (let a= p1^k1*p2^k2 ...)
Then we need to look for n in the form k*p1*p2*...
This is the same k, we need to sort through from 1 to the maximum ki and check that n^n is divisible by a. To do this, you need to count how many times k is divided by p_i (let it be q_i). Then we need to check that, (q_i+1)*n >= k_i for all prime divisors p_i.

Answer 2

Damn you made it harder.
Something like this would be
n = 1
y = 0
Loop over all prime factors:
xi - current prime factor
yi - number of times xi occurs
n = n*xi
y = max(y, yi)
End of loop
If n < y then n = n * ceil(y/n)
Answer n.