约数个数定理

本文主要是介绍约数个数定理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

int div(int x){
            int i,s,r;
            for (i = 2; i * i <= n; i++) {
                r = 0;                                       //指数
                while (n % i == 0) {                         //循环分解质因数
                    r++;                                     //因数的指数
                    n /= i;                                   
                }
                if (r > 0) {
                    r++;
                    s *= r;
                }
            }
            if (n > 1)
                s *= 2;
            return s;
}        

对于大于1的正整数可以写成分解质因数的形式

p₁,p₂,...为素数.

约数个数定理

p₁,p₂,...的指数a_1,a₂,a_3...

记为r.

此外还需要用到该定理:　 

  定理1：就是给定一个数n,在√n的右边整数里只有至多有一个质数.

        　　证明：假设√n的右边有两个质数p₁,p₂,那么p_1*p₂≥n与题干矛盾，因此至多只有一个质数

 算法

首先,找到所有小于等于√n的 所有素数,然后求出对应的指数,接着用约数个数定理,

接着在√n有边可能还有一个素数,如果有则约数个数为2*r

，这是因为该素数可以跟√n左边的任何一个相乘成为约数，因此约数翻倍；如果没有的话约数个数就是r.　　　

这篇关于约数个数定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！