P16168 [ICPC 2015 NAIPC] Primal Partitions

数学系向你所在大学的计算机科学系发起挑战，要求解决离散数学中的一个难题。为了计算机科学系的荣誉，你必须解决这个难题！ 在这个难题中，你得到一串由 $n$ 个正整数组成的序列。你需要将这个序列划分成 $k$ 个连续的区域，每个区域至少包含 $1$ 个整数。找到一种划分后，将用一种奇怪的方式计分。在每个区域中，你必须找到能整除该区域内每个整数的最大素数。数学系提醒你，素数是大于 $1$ 且只有 $1$ 和自身两个因数的整数。如果找不到这样的素数，则该区域的得分为 $0$。划分的总得分是所有区域得分的最小值。 你的任务是找到可能的最大得分。如果数学系的得分更高，他们就赢了，所以请务必每次都找到最大得分！

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入的第一行包含两个空格分隔的整数 $n$（$1 \leq n \leq 20000$）和 $k$（$1 \leq k \leq \min(100, n)$），其中 $n$ 是原始序列中正整数的个数，$k$ 是划分中的区域个数。下一行包含 $n$ 个空格分隔的整数 $v$（$1 \leq v \leq 1{,}000{,}000$），表示要划分的原始序列（按顺序）。

输出一个整数，表示将 $n$ 个正整数的序列划分成 $k$ 个区域时可能获得的最大得分。

翻译由 DeepSeek V3.2 完成