约数个数定理：

对于一个大于1正整数n可以分解质因数：

则n的正约数的个数就是

。

定理简证：

例题：

约数和定理：

定理证明：

例题：

所有因子个数τ（n）与所有因子的和σ（n）都是乘（积）性函数。

定义1：因子和函数σ定义为整数n的所有正因子之和，记为σ（n）。

定义2：因子个数函数τ定义为正整数n的所有正因子个数，记为τ（n）。

定理1：设p是一个素数，a是一个正整数，那么

                                σ（n）=1+p+p^2+……+p^a=【p^(a+1)-1】/(p-1)

                                τ（n）=a+1

定理2：设正整数n有素因子分解 n =（p1^α1）*（p2^α2）*（p3^α3）* ……. *（pk^αk），那么

             σ（n）=【（p1^α1）-1】/（p1-1） * 【（p2^α2）-1】/（p2-1） * …..  *【（pk^αk）-1】/（pk-1）

             τ（n）=（α1+1）*（α2+1）*（α3+1）*……*（αk+1）

求因子个数：

int prime[maxn],nprime;  
int vis[maxn];  
  
void getprime(){
    nprime = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 2; i <= 450; i++){
        int t = 450/i;
        for(int j = 2; j <=t; j++)
            vis[i*j] = 1;
    }
    for(int i = 2; i <= 450; i++){
        if(!vis[i])
            prime[nprime++] = i;
    }
}
  
int factor_count(int n){  
    int ans = 1,sum;  
    int k = sqrt(n*1.0);  
    for(int i = 0; prime[i] < k; i++){  
        if(n % prime[i] == 0){  
            sum = 0;  
            while(n % prime[i] == 0){  
                sum++;  
                n /= prime[i];  
            }  
            ans *= (a+1);  
        }  
    }  
    if(n > 1)  
        ans *= 2;  
    return ans;  
}  

求因子和：

int prime[maxn],nprime;
int vis[maxn];

void getprime(){
    nprime = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 2; i <= 450; i++){
        int t = 450/i;
        for(int j = 2; j <=t; j++)
            vis[i*j] = 1;
    }
    for(int i = 2; i <= 450; i++){
        if(!vis[i])
            prime[nprime++] = i;
    }
}

int pow_mod(int a,int n,int MOD){
    int ans = 1;
    while(n){
        if(n&1)
            ans = (ans*a)%MOD;
        n >>= 1;
        a = (a*a)%MOD;
    }
    return ans;
}

int factor_sum(int n){
    int ans = 1,sum;
    int k = sqrt(n*1.0);
    for(int i = 0; prime[i] < k; i++){
        if(n % prime[i] == 0){
            sum = 0;
            while(n%prime[i] == 0){
                sum++;
                n /= prime[i];
            }
            ans *= (pow_mod(prime[i],sum+1,MOD)-1)/(prime[i]-1);
        }
    }
    if(n > 1)
        ans *= ans(n*n-1)/(n-1);
    return ans;
}

今天的文章约数定理（约数个数定理，约束和定理）分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。