有一组数字,怎样快速组合相加后的结果等于或接近另一个数字,但不能大于另一个数字?

Question

有一组数字,怎样快速组合相加后的结果等于或接近另一个数字,但不能大于另一个数字?

Answer 1

对比较小的数来说方法是首先做质因数分解,然后把每个质因数指数系数+1再相乘,比如
28 = 2^2 * 7,总共有3 * 2 = 6个数能整除它,包括它自己和1：1 2 4 7 14 28
从排列组合原理上很好解释这个方法.
但是你都知道对于密码学意义上的“数”来说分解有多困难了,这个方法当然不行.
只有一个方法粗判断这个数是不是一个质数,运用费马小定理的（伪）逆定理：
费马小定理：
a ^ (p-1) = 1 (mod p)
对于任意a < p都成立.
比如3^4 = 81 = 1 (mod 5)
这个证明到处都有
而如果对于某个p和a（a ...