素数伴侣
若两个正整数的和为素数,则这两个正整数称之为"素数伴侣"
判断素数:
- 不是偶数且不能被5整除且不能被小于它的平方根(因为大于平方根的数的另一个乘数必须小于它,小于平方根的数已经被测试过了)的所有奇数整除
- 正则非贪婪匹配再判断是否整除 !/^.?$|^(..+?)\1+$/.test(Array(num+1).join('1'))
匈牙利算法:
- 将输入的奇数偶数分两组,建立二分图,两两相组合能得到素数的就赋 1;
- 再建立全局的连接表 modd 和 meven,记录该奇数(偶数)连接的偶数(奇数);
- 然后遍历每个奇数,每个奇数在寻找合适的偶数时,建立一个 visit 记录在该轮查找中已经搜过的偶数,匈牙利的原则就是"先到先得,能让就让,不能让就拜拜",所以在确定合适偶数对象时,如果该偶数没有被配对过,直接绑定,若它被配对了,那就让配对它的那个奇数再去找其他的偶数进行配对,以此类推进行递归,若到了某个位置发现找到了,则这条新的配对方案建立,比之前的配对个数多了 1,若没找到,则保持原先的方案。