思路：数论

所有大于1的合数均可以表示为若干个素数的积，即$x=p_{1}^{k_1}*p_{2}^{k_2}*...*p_{n}^{k_n}$

所以我们只需要找到$x$的一个素因子$k$，那么答案即为$x/k$

由于$n$最大为$10^5$，所以我们只需要筛一次素数，然后再判断即可。

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int testCases = input.nextInt();

        while (testCases-- > 0) {
            int number = input.nextInt();
            boolean isPrime = true;

            for (int divisor = 2; divisor * divisor <= number; divisor++) {
                if (number % divisor == 0) {
                    System.out.println(divisor);
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.println(number);
            }
        }
    }
}

C++

#include <bits/stdc++.h>

using namespace std;

int main(){
    int k = 0;
    cin >> k;
    int num = 0;
    while(cin >> num){
        // 任何一个大于1的数都是可以表示为若干素数的乘积
        // （n,m）的最大公约数是素数，则只需要找到一个素数p使得n%p == 0，p就是m
        bool flag = true;   // 标志自身是不是素数
        for(int i = 2; i*i <= num; ++i){
            if(num % i == 0){
                cout << i << endl;
                flag = false;
                break;
            }

        }
        if(flag){
            cout << num << endl;
        }

    }

    return 0;
}

题目描述

小乖对 $gcd$ (最大公约数) 很感兴趣, 他会询问你$t$次。 每次询问给出一个大于 $1$ 的正整数 $n$, 你是否找到一个数字$m(2 ≤m ≤ n)$，使得 $gcd(n, m)$ 为素数.

注：原题为给出任意解，本题中请给出最小值作为答案

输入描述

每个测试文件将包含多组测试数据,每组测试数据的第一行包含一个整数 $k (2 ≤ k ≤ 10^5)$, 表示有$k$ 个待测数字.接下来 $k$ 行,每行包含一个整数$n (2 ≤ n ≤ 10^9)$,表示待测的数字.

输出描述

对于每一组测试数据, 在一行上输出一个整数，代表数字 $m$。

示例 1

输入

2
114
15

输出

2
3