#include <cstdio>
bool Is_not_it_a_prime_number(int n)
{
    for (int i = 2; i < n / 2; i++)
    {
        if (!(n % i))
        {
            return 1;
        }
    }
    return 0;
}
int Prime_factorization(int n)
{
    int i, k = n / 2;
    do
    {
        for (i = k; n % i; i--)
        k = i;
    }while (Is_not_it_a_prime_number(i));
    return i;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", Prime_factorization(n));
    return 0;
}

输入 $45(5 \times 9)$ 就超时了，按理来说应该输出 $5$ 啊？