正约数个数：
若一个正整数N能够被分解为N=(p₁^a₁)(p₂^a₂)(p₃^a₃)(p₄^a₄)...，
则N的正约数的个数为（a1+1)*(a2+1)*(a3+1)*...
原理(来自百度百科）：
由约数定义可知p1^a1的约数有:p^0, p^1, p^2, ..., ，共（a1+1）个；
同理的p2^a2的约数有（a2+1）个； pk^ak的约数有（ak+1）个。
故根据乘法原理：n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。
如下例：
试除法求N的正约数集合。
对于N来说，任何一个约数都可以通过d<=√N得到，若N%d==0，则有一个对应的大于等于d的数字也是N的约数。
因此可以扫描1到√N的数字即可得到N的所有约数。
试除法推论：一个整数N的约数上限为2*（√N）。
#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
int factor[N],cnt;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
factor[++cnt]=i;
if(i!=n/i)
factor[++cnt]=n/i;
}
}
sort(factor+1,factor+cnt+1);
for(int i=1;i<=cnt;i++)
{
printf("%d ",factor[i]);
}
return 0;
}
倍数法求1~N所有数的约数：
用试除法求1~N所有数的约数时间复杂度为O（N*√N）。
从约数的角度考虑，以d为约数的数一定是d,2*d,3*d,4*d,....⌊N/d⌋*d。
时间复杂度为O(N+N/2+N/3+...+N/N);
#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
vector
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
{
factor[i*j].push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j printf("%d ",factor[i][j]); puts(""); } return 0; }