阿狗工具

今天在刷牛客网华为机试的题目。

有个素数伴侣的算法，就是在给定一组数字中，例如2，3，5，6，11，13，找出能够配对最多的素数对数（素数：不能被除了1和本身之外的数整除）。比如2+3就是一个素数，这俩就是一对素数伴侣，剩下四个数以此类推找出最大配对数。

题目很好懂，如果给一个例子自己算也很好算，但就是自己的计算也没有规律可言，都是肉眼找。

思来想去找不到计算规律，查看题解才知道，原来有一个匈牙利算法，可以解决此类问题。这个算法的核心可以用八个字概括：先到先得，能让则让。

简单来说我们的数字列表可以分为奇数和偶数两对，只有奇数+偶数的组合才可能是素数。

也就是说我们其实是在给奇数项和偶数项画连接线。

先到先得意思是如果第一个奇数和第一个偶数加起来是素数，就可以作为一对伴侣。

能让则让意思是，如果第二个奇数和第一个偶数也能配对，那么第一个奇数考虑把原来配对的偶数让出去。如果能找到新的偶数伴侣的话。

假设第一个奇数找到了第三个偶数配对成功，那么第二个奇数就可以找第一个偶数，这样就有两对了。以此类推可以解决素数伴侣的问题。

看完算法的说明我其实是蒙圈的，为什么先到先得能让则让就可以找到最优解？原理是什么呢？谁想到的这么解呢？

找了一些资料也没有发现通俗地说法，只能解释为这背后有数学理论作为依据。

看来算法的本质是数学啊，还得学好数学，才能做好算法。