一带一路是去去年习大大提出来的建设“新丝绸之路经济带”和“21世纪海上丝绸之路”的战略构想。其中就包括我们新疆乌鲁木齐，所以这也是对新疆来说是一个巨大的机遇。我们新疆要加强和周边国家的经济文化交流，就必然要和周边国家城市修许多路。现在假设有N座城市，每一个城市都有一个投资指标数，例如A城市和B城市的投资指标数分别为Ia和Ib，如果Ia或Ib或Ia-Ib的绝对值为素数或者为1，则A城市和B城市可以修路，否则不能。他们修路的花费为Ia，Ib，Ia-Ib的绝对值这三个数中的最小值，并且为素数或者1。现在已知所以城市之间的投资指标，假设他们直接原来没有任何路，要求你在其中修路联通这些城市（即任何两座城市之间都能直接或者间接的有路相通）。求修这些路最少花费总和。

输入包含多组数据，第一行为测试数据T组（1<=T<=10）;以下每组数据第一行包含城市的个数N(1<N<=100)，接下来一行表示N个整数表示每个城市的投资指标数I（I为正整数，1<=I<=1000000）

输出最小花费总和，如果无法使所以城市连通，则输出-1

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

int a[];

int s[][];  //邻接矩阵 

//O(n)的素数筛选，见小红书算法与实现

int ans[]; //按顺序记录素数

bool valid[]; // valid[i] == true 表示 i是素数

int tot = ;   //素数的个数

void getPrime(int n){

    memset(valid,true,sizeof(valid));

    for(int i = ;i <= n; i++){

        if(valid[i]){

            tot++;ans[tot] = i;

        }

        for(int j = ;((j <= tot)&&(i*ans[j] <= n)); j++){

            valid[i*ans[j]] = false;

            if(i&ans[j] == ) break;

        }

    }

}

int mincost[]; //记录从源点0到点i的最小花费

bool used[];   // 记录i点是否使用过 

int prim(int n){

    for(int i = ;i < n; i++){

        mincost[i] = 2e9;

        used[i] = false;

    }

    mincost[] = ;

    int res = ;

    while(true){

        int v = -;

        for(int u = ;u < n; u++){

            if(!used[u] && (v == - || mincost[u] < mincost[v])) v = u;

        }

        if(v == -||mincost[v] == 2e9) break;

        used[v] = true;

        res += mincost[v];

        for(int u = ;u < n; u++){

            mincost[u] = min(mincost[u],s[v][u]);

        }

    }

    //判断是否有点没有用过，即不能产生最小生成树

    int flag = ;

    for(int i = ;i < n; i++){

        if(!used[i]){

          flag = ;

          break;

        }

    }

    if(flag) return -;

    if(res <= ) return -;

    return res;

}

int main()  {  

    //O(n)的素数筛选

    getPrime();

    int t,n;

    cin >> t;

    int num = ;

    while(t--){

        for(int i = ;i < ; i++){

            for(int j = ;j < ; j++){

                s[i][j] = 2e9;

            }

        }

        cin >> n;

        for(int i = ;i < n; i++){

            cin >> a[i];

        }

        for(int i = ;i < n; i++){

            for(int j = i+;j < n; j++){

                //找到3个数中最小的素数

                int p = abs(a[i]-a[j]);

                int d[] = {p,a[i],a[j]};

                sort(d,d+);

                for(int k = ;k < ; k++){

                    if(valid[d[k]]){

                        //如果为素数则跳出，此时是最小的素数

                        s[i][j] = d[k];

                        s[j][i] = d[k];

                        break;

                    }

                }

                //没有素数，即不产生一条边

                if(s[i][j] == ) s[i][j] = 2e9;

            }

        }

        cout << "Case " << ++num << ": ";

        cout << prim(n) << endl;

    }

  return ;

}