当前位置：首页 > article >正文

因子(Number_Of_Factors)

article 2025/7/1 4:43:10

一、定义

因子：假如整数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{//包含1System.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_43272781/article/details/85058735

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

公因子都是以相反数形式成对出现的，所以一般研究正因子就够了。这样,4和6的公因子为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_43272781/article/details/86547908

八、完数

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;}}