数论学习之约数

本文主要是介绍数论学习之约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近学数论真的感觉自己脑子很不好用啊，一个证明题想半天。
感觉一些基础的知识还是比较重要的，所以就记录下来吧，加深一下印象。
对于一个整数n，假如我们想求到这个整数的所有的约数的话，我们只要对其$1-\sqrt{n}$之间找可以被n整除的那些数，然后就可以找到它们的约数了。时间复杂度$O(\sqrt{n})$.
代码：

//试除法
int factor[1600],m=0;
for(int i=1;i*i<=n;i++){if(n%i==0){factor[++m]=i;if(i!=n/i)  factor[++m]=n/i;}
}

但是，如果我们一次求出1-n之间的所有的数的约数的话，我们肯定是不能用这种低效的方法的。接下来，我们来介绍一下倍除法，我们发现，对于每个数d，1-n之间以d为约数的数有d，2d，3d…[n/d]d，那么我们就可以利用线性求解的方法来进行处理。时间复杂度为$O(nlogn)$
代码：

//倍除法
vector<int> factor[1500];
for(int i=1;i<=n;i++){for(int j=1;j<=n/i;j++){factor[j*i].push_back(i);}
}

接下来，介绍一个名词：反素数
我们用g(x)表示一个数x的约数的个数，对于任意的0<i<x的数，都有g(x)>g(i)的话，那么就称这个数为反素数。
还有一些引理：
1、1-N之中任何数的质因子都不会超过10个，而且每个质因子的个数不会超过30个，这个由于10！个数和2^30的范围就可以得到。
2、如果一个数x为反素数的话，那么x的分解质因数后可以写作$2^{c_1}\ast 3^{c_2}\ast ...29^{c_{10}}$,而且c1>=c2>=c3>=c4>=c5…>=c10,也就是这些质数的指数都是单调非递增的。

这篇关于数论学习之约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---