[BCSP-X 2024 6 月小学高年级组] 最小质因子

Luogu

IDLGB4170

Time1000ms

Memory512MB

DifficultyP2

2024北京素数判断,质数,筛法BCSP-X

给定一个正整数 $n$，设 $n = p_1 \times p_2 \times \dots \times p_k$，其中 $p_i$ 均为质数，对 $1 \leq i < k$，$p_i \leq p_{i+1}$。给定 $n$，请你计算其最小的质因子 $p_1$。例如： - $36 = 2 \times 2 \times 3 \times 3$，最小质因子是 $2$； - $49 = 7 \times 7$，最小质因子是 $7$； - $89 = 89$，最小质因子是 $89$； - $967217 = 37 \times 26141$，最小质因子是 $37$； ## Input 第一行 $1$ 个整数 $T$，代表有 $T$ 组数据。接下来 $T$ 行，每行 $1$ 个整数 $n$。 ## Output 输出 $T$ 行，每行 $1$ 个整数 $p_1$ 代表答案。 [samples] ## Note ### 数据范围对于所有数据，$1 \leq T \leq 50, 1 < n \leq 10^{12}$。 - 对于测试点 1~8：$n \leq 1000$； - 对于测试点 9~14：$n \leq 10^5$； - 对于测试点 15~17：$n \leq 10^9$； - 对于测试点 18~20：$n \leq 10^{12}$；

Samples

Input #1

14
36
2
3
49
81
35
12
89
16
100
967217
917597
185971
43607027731

Output #1

2
2
3
7
3
5
2
89
2
2
37
571
185971
43607027731

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 6 月小学高年级组] 最小质因子",
    "description": {
      "content": "给定一个正整数 $n$，设 $n = p_1 \\times p_2 \\times \\dots \\times p_k$，其中 $p_i$ 均为质数，对 $1 \\leq i < k$，$p_i \\leq p_{i+1}$。 给定 $n$，请你计算其最小的质因子 $p_1$。 例如： - $36 = 2 \\times 2 \\times 3 \\times 3$，最小质因子是 $2$； - $49 = ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4170"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$，设 $n = p_1 \\times p_2 \\times \\dots \\times p_k$，其中 $p_i$ 均为质数，对 $1 \\leq i < k$，$p_i \\leq p_{i+1}$。\n\n给定 $n$，请你计算其最小的质因子 $p_1$。\n\n例如：\n- $36 = 2 \\times 2 \\times 3 \\times 3$，最小质因子是 $2$；\n- $49 = ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments