约数——正约数个数求法及其原理，求N的正约数集合

正约数个数：

若一个正整数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> factor[N];
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;jsize();j++)
        printf("%d ",factor[i][j]);
        puts("");
    }
    return 0;
}