Problem E
Primal Partitions
The Math department has challenged the Computer Science department at your University to solve a difficult puzzle in Discrete Mathematics. With the pride of your Computer Science department at stake, you must solve this puzzle!
In this puzzle, you are given a sequence of $n$ positive integers. The sequence must be partitioned into $k$ consecutive contiguous regions, with at least 1 integer in each region. After finding a partition, it is scored in a strange way. In each region, you must find the largest prime number that divides every number in that region. The Math department reminds you a prime number is an integer greater than 1 where its only divisors are 1 and itself. If you cannot find such a prime, your score for that region is 0. Your total score for the partition is the minimum over all regions.
Your task is to find the maximum possible score. The Math department will win if their score is better, so be sure to find the maximum each time!
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input begins with a line with two space-separated integers $n$ ($1 \le n \le 20\, 000$) and $k$ ($1 \le k \le \min (100,n)$), where $n$ is the number of positive integers in the original sequence, and $k$ is the number of regions in the partition. The next line contains $n$ space-separated integers $v$ ($1 \le v \le 1\, 000\, 000$). This is the sequence to be partitioned, in order.
Output
Output a single integer representing the maximum score possible partitioning the sequence of $n$ positive integers into $k$ regions.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 10 5 4 8 3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 10 11 12 13 14 |
0 |
