如何寻找最接近根号n的n的因子

lsrong314

给定一个整数n的分解式，如何寻找最接近的整数a和b，使ab=n?
这个问题可以等价的表述成：如何在一个集合（可以有相同的元素，下同）里提取一个子集，使得其元素之和最接近原集合元素之和的一半？

liangbch

若$N=(P_1^{e_1})(P_2^{e_2})...(P_n^{e_n})$
则N的因子个数为$(e_1+1)(e_2+1)...(e_n+1)$
算法，将n的所有因子找出来，并排序，取中间的2个。
如60=$2^2xx3^1xx5^1$,则60有$(2+1)xx(1+1)xx(1+1)=12$个因子，它们是1,2,3,4,5,6,10,12,15,20,30,60. 居于中间的2个因子是6和10

liangbch

给定一个整数n的分解式，如何寻找最接近的整数a和b，使ab=n?
这个问题可以等价的表述成：如何在一个集合（可以有相同的元素，下同）里提取一个子集，使得其元素之和最接近原集合元素之和的一半？
lsrong314 发表于 2012-2-14 12:31

这两个问题并不等价？

lsrong314

3# liangbch
取对数就变成在ei个log(pi)，i=1,2……里提取元素的问题

liangbch

2# liangbch
2#方法的另一种描述，若f是n的一个因子，且f<=sqrt(n), 所有满足条件的f构成一个数组a,则x1=MAX(a), x2=n/x1, MAX(a)函数返回数组a中各个元素的最大值. x1,x2即为答案。