怎么求一个数的约数？
有一个题目要求求出一个特定区间的合数中约数最多的数并输出相应的约数个数。我写了一个算法，但效率太低。请高手指教。
#include <iostream>
#include <cmath>
int run (int n)
{
int i;
int m=n/2;
int sum=0;
for (i=1; i <=m; ++i)
{
if (n%i==0)
{
++sum;
}
}
return sum+1;
}
bool isZh (int n)
{
int m=std::sqrt(n);
int i;
for (i=2; i <=m; ++i)
{
if (n%i==0)
{
return false;
}
}
return true;
}
int main(int argc, char *argv[])
{
int a,b;
std::cin> > a> > b;
int i;
int max=0;
int x;
int sum;
for (i=a; i <=b; ++i)
{
if (isZh(i))
{
sum=2;
}
else
{
sum=run(i);
}
if (max==0 || sum> max)
{
max=sum;
x=i;
}
}
std::cout < <x < < " " < <max < <std::endl;
return 0;
}
[解决办法]
做表吧，比如说这个特定区间的合数区域为1000--10000;
先做个素数表，比如到10000的素数表prime[5000];
然后再查找就方便了，不用1到n去遍历；
找到它的所有约数，相当于因式分解。
然后用排列组合的知识，很快就可以知道它有几个约数了。
[解决办法]
如果一个大于 1 的正整数 N 的素因数分解式是：
N = p[1]^m[1] × p[2]^m[2] × … × p[n]^m[n]
其中 p[1]、p[2]、……、p[n] 是 素数，而且
p[1] < p[2] < …… < p[n]，
m[1]、m[2]、……、m[n] 是正整数。根据排列组合的知识， N 的约数的个数为
(m[1]+1) × (m[2]+1) × …… × (m[n]+1)
所以，问题的核心就在于怎样快速因式分解。方法就像gjlzjb() 所说的。
[解决办法]
约数（除了平方跟）都是成对的，实际上只需要检查2到其平方根之间的数就可以了就可以了；
int max=0;
for (i=a; i <=b; ++i)
{
int count=0; //如果包括平凡约数，则count的初始值为2；
int k=sqrt(i);
if (k*k==i) count++;
for (j=2;j <k;++j)
{
if (i%j==0) count+=2;
}
if (count> max) max=count
}
[解决办法]
可先采用筛选法筛选出一部分后再求最大值：
1、由于非素数的约数个数总是> =素数的约数个数：因此可以筛选出a-b中的素数，只求非素数即可。采用if（素数） 跳出即可。
2、x1和x2，如果x1/x2==0。则x1约数个数> =x2的约数个数，利用此原理可筛选出a-b中部分数据，
经过2次筛选，然后采用上述各大侠提出的方法比较a-b剩下的数据，可大大提高算法效率。
