一、定义

因子：假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因子。

质因子：在数论里，某一正整数的质因子指能整除该数的质数整数。

完数：一个数的因子之和等于它本身，则该数为完数。

二、性质

1、因子性质

无

2、质因子性质

两个没有共同质因子的正整数称为互质。

数字1与任何正整数（包括1 本身）都是互质。

This is because it has no prime factors; it is the empty product。

正整数的因数分解给出一连串的质因子；所有质因子相乘后。质因子如重复会以指数表示。

根据Fundamental theorem of arithmetic，任正整数有独一无二的质因子分解式。

设任正整数n，其质因子数目及其质因子的和是n的算术函数(arithmetic function)。

例子 6的质因子是3和2。(6 = 3 × 2) 5只有1个质因子，5本身。（5是质数。）

100有2个质因子：2和5。(100 = 2 x 50, 且100=5 x 20，只有2和5是质数)

2、4、8、16等只有1个质因子：2（2是质数，4 = 2 x 2，8 = 2 x 4，如此类推。偶数(6除外)的因子中，只有2是质数。）

1没有质因子。（1是empty product）

3、

三、定理

1、任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 这里P_1<P_2<...<P_n是质数，其诸方幂 ai 是正整数。

这样的分解称为N 的标准分解式。

2、对于任意的整型N，分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn;

则N的因子个数M为 M=（x1+1） * （x2+1） * …… *（xn+1）;

证明：

24 = 2^3 * 3^1；

其质因子有：为2和3  指数为 3和1

那么对于2 有0 1 2 3四种指数选择，对于3 有0 1两种指数选择

所以 就是4 * 2 = 8 个因子个数

如果还是不懂，那么我们就列举出来吧

2 3

2^0*3^0=1             2^0*3^1=3

2^1*3^0=2             2^1*3^1=6

2^2*3^0=4             2^2*3^1=12

2^3*3^0=8             2^3*3^1=24

结果很清晰了吧？？其实这里用到了数学的排列组合的知识

也就是说每一个质因子的不同指数幂与其它质因子相乘，得到的结果一定不会重复

因此能够将所有的因子都列举出来。

所以N的因子数M，我们可以用M=（x1+1） * （x2+1） * …… *（xn+1）表示

​​

讯享网

3、

四、判断是否是某个数的因子

假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因子。

五、求因子及个数

1、朴素一般方法

枚举1-N，计数

C++版本一

void getFactors(int n){ int cnt=0; for(int i=1;i<=n;i++){ if(n%i==0){ printf("%d ",i); cnt++; } } printf("\n%d\n",cnt); }

2、简单优化方法

C++版本一

讯享网void getFactors(int n){ int cnt=0; int q=sqrt(n); int a[n]; for(int i=1;i<=q;i++){ if(n%i==0){ a[++cnt]=i; if(i*i!=n) a[++cnt]=n/i; } } sort(a+1,a+cnt+1); for(int i=1;i<=q;i++){ printf("%d ",a[i]); } printf("\n%d\n",cnt); }

JAVA版本一

 / * 求一个数的因子,这里值的是正因子，包含1，但不包含本身。 * @param n 自然数 * @return 因子的个数 */ public static int getFactors(int n){ int count = 0; if(n == 0) return count; else if(n == 1 || n == 2){ System.out.println("n"); return ++count; } else{ //包含1 System.out.print(1+" "); int l = (int) Math.sqrt(n); for(int i = 2; i <= l; i++){ if(n % i == 0){ System.out.print(i+" "); System.out.print(n/i+" "); count += 2; } } } return count+1; } 

3、普通筛

讯享网 for(int i=1; i<=maxm; i++){ for(int j=i; j<=maxm; j+=i) fla[j]++; }

4、线性筛

参考文章：https://blog.csdn.net/weixin_/article/details/

C++版本一

int D[M]; int pre[M]; bool prime[M]; D[1]=1; prime[0]=prime[1]=1; for(int i=2;i<M;i++){ if(!prime[i]){ D[i]=2; pre[++cnt]=i; } for(int j=1;j<=cnt&&i*pre[j]<M;j++){ prime[i*pre[j]]=1; D[i*pre[j]]=D[i]*2; if(i%pre[j]==0){ int c=1; t=i; while(t%pre[j]==0){ t/=pre[j]; c++; } D[i*pre[j]]=D[t]*(c+1); break; } } //cout<<i<<" "<<D[i]<<endl; }

六、求质因子及个数

C++版本一

讯享网#include<iostream> #include<cstring> using namespace std; int main(){ long a; int k=0; int b[100]; cin>>a; for(int i=2;i<=a;i++){ while(a%i==0){ a/=i; b[k]=i; k++; } } for(int i=0;i<k;i++) cout<<b[i]<<' '; return 0; } 

JAVA版本一

 / * 求一个自然数的质因子 * @param n 自然数 * @return 质因子个数 */ public static int getFactorsByPrimeNumber(int n){ LinkedList<Integer> list = new LinkedList<Integer>(); list.add(2); int m = n; if(n == 0 || n ==1) return 0; else{ if(Day1.isPrimeNumber(m)){ list.add(n); System.out.print(n+"= 1*"+n); return 1; }else{ int curLast = 0; while(!Day1.isPrimeNumber(m)){ curLast = list.getLast(); while(true){ if(Day1.isPrimeNumber(curLast)){ if(m % curLast == 0){ list.add(curLast); m = m / curLast; break; } } curLast++; } } list.add(m); //打印输出 int valuse = list.get(1); int count = 1; System.out.print(n+"="+valuse); for(int i = 2; i < list.size(); i++){ System.out.print("*"+list.get(i)); if(valuse != list.get(i)){ count++; valuse = list.get(i); } } return count; } } } 

七、求公因子及个数

1、公因子

定义：

设a,b是两个整数，若c是整数，且c整除a,则c称为a的一个因子（或约数），a的所有约数组成一个非空集合（设为A），b的所有因子组成集合B，设A∩B=C,称C的元素为a和b的公因子，显然C非空，因为至少1属于C。

如4和6的所有公因子为1,2，-1,-2

JAVA版本一

讯享网/ * 求两个数的公因子 * 思路： * 1. 先求两个数的公约数 * 2. 对最大公约数进行求因子。如果该公约数为所求两个数较小的数，则公因子不包括该数，否则则包括 * 比如 30 15 最大公约数为15 公因子为 1 3 5 * 比如 20 8 最大公约数为4 公因子为 1 2 4 * @param n m 参数 * @return 公因子个数 */ public static int getAllFactors(int n,int m){ int count = 0; if(n ==0 || m ==0) return 0; else{ //调用最大公约数函数 int greatestCommonMeasure = Tools.getGreatestCommonMeasure_2(n, m); if(greatestCommonMeasure == 0){ return greatestCommonMeasure; }else if(greatestCommonMeasure == 1){ System.out.println(1+" "); return greatestCommonMeasure; }else{ System.out.print(1+" "); count++; if(greatestCommonMeasure != n && greatestCommonMeasure != m){ count++; System.out.print(greatestCommonMeasure+" "); } int l = (int) Math.sqrt(greatestCommonMeasure); for(int i = 2; i <= l; i++){ if(greatestCommonMeasure % i == 0){ System.out.print(i+" "); System.out.print(greatestCommonMeasure/i+" "); count += 2; } } } return count; } } 

2、最大公因数

参考文章

https://blog.csdn.net/weixin_/article/details/

八、完数

1、判断

#include <iostream> using namespace std; int main() { int sum=0; int n; cin>>n; for(int i=1; i<n; i++)//这里可以换成int i=1;i<=n/2;i=i+2 { if(n%i==0) { sum=sum+i; } } if(sum==n) { cout<<"yes"<<endl; } else { cout<<"no"<<endl; } } 

2、区间内的完数

讯享网#include <fstream> #include <iostream> #include <vector> using namespace std; int main(int argc, char* argv[]) { vector<int>a; //创建向量 for(int i=2; i<10000; i=i+2)//先把小于10000的完数找出来 { int sum=1; for(int j=2; j<=i/2; j++) { if(i%j==0)sum=sum+j; } if(sum==i)a.push_back(i); } int n; cin>>n; for(int i=1; i<=a.size(); i++) { if(a[i]<n) cout<<a[i]<<endl; } } 

九、例题

https://codeforces.com/problemset/problem/236/B（题解：https://blog.csdn.net/weixin_/article/details/）

http://acm.hdu.edu.cn/showproblem.php?pid=5970

https://codeforces.com/problemset/problem/920/F（题解：https://blog.csdn.net/weixin_/article/details/）

十、参考文章

https://blog.csdn.net/u0/article/details/

https://blog.csdn.net/weixin_/article/details/

https://blog.csdn.net/a1b2c3d/article/details/

https://blog.csdn.net/yanglong_blog_/article/details/