题解 | #素数伴侣#

这是一个超时的题解， 用的是最呆的穷举+递归。（因为算法什么的都不会，所以只能是靠蛮力了(ಥ_ಥ) ） 这里显示5组通过。（mgj的题目也不说测试用这么多用例，还这么大的数。

不然我也不写了(╬￣皿￣)=○）

因为这里没有实际输出。 所以我又粘贴到其他c语言在线网站试了一下。看样子至少也算是解出来了，算是没全白费功夫。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
                                                         
#define u16 unsigned short

/**
 * @brief   判断是否是素数伴侣
 * @param   val1 数1
 * @param   val2 数2
 * @return  伴侣数量
 */
u16 If_PrimeMate(u16 val1, u16 val2)
{
    int val = val1 + val2;
    int mid = (int)sqrt((double)val);
    
    for(int i = 2; i <= mid; i++)
        if(val % i == 0)
            return 0;//能被整除
    
    return 1;
}

/* 
* @brief 获取素数伴侣的最多数目
* @param src 需要搭配的正整数数组
* @param num 正整数个数
* @return 素数伴侣的最多数目
*/
u16 Get_Max_PrimeMate(u16 *src, int num)
{
    //使用递归，只有两个数时，直接搭配
    if(num == 2)
        return If_PrimeMate(src[0],src[1]);
    
    u16 max_num = 0;
    
    //轮询所有正整数的两两组合
    for(int i = 0; i < num-1; i++)
        for(int j = i+1; j < num; j++)
        {
            u16 result = 0;
            
            //求挑选出来的两个数是否是"素数伴侣"
            result += If_PrimeMate(src[i],src[j]);
            
            //将数组src中的src[i]和src[j]剔除，重新组成一个数组（内存块）。
            //注：这里src其他元素的顺序是不变的。但是否有序不影响结果，这里只是想把剩余的元素组成内存块，便于调用。
            u16 *temp = (u16 *)malloc(sizeof(u16) * (num - 2));
            memcpy(temp,src,sizeof(u16) * i);                        //将src的前 i 个数拷贝到temp
            memcpy(&temp[i],&src[i+1],sizeof(u16) * (j-i-1));        //将src[i] 到 src[j]之间的数拷贝到temp的后面（接着上一次拷贝的地址）
            memcpy(&temp[j-1],&src[j+1],sizeof(u16) * (num-j-1));    //将src[j]后面的数拷贝到temp的后面（接着上一次拷贝的地址）
            
            //寻找挑选剩下的数的“素数伴侣”个数
            result += Get_Max_PrimeMate(temp, num-2);
            
            free(temp);
            
            //找到最大的数
            if(result > max_num)
                max_num = result;
        }
    
    return max_num;
}

int main(void)
{
    u16 recv_num[100],n;
    
    while(scanf("%d",&n) != EOF)
    {
        for(int i = 0; i < n; i++)
            scanf("%d",&recv_num[i]);
        
        printf("%d\n",Get_Max_PrimeMate(recv_num,n));
    }
    
    return 0;
}