一、定義

因子：假如整數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;}}

九、例題

https://codeforces.com/problemset/problem/236/B（題解：https://blog.csdn.net/weixin_43272781/article/details/86585021）

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

https://codeforces.com/problemset/problem/920/F（題解：https://blog.csdn.net/weixin_43272781/article/details/86584055）

十、參考文章

https://blog.csdn.net/u010794180/article/details/48860927

https://blog.csdn.net/weixin_43272781/article/details/86547908

https://blog.csdn.net/a1b2c3d4123456/article/details/50410028

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

總結

以上是生活随笔為你收集整理的因子(Number_Of_Factors)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。