整数唯一分解定理(Unique decomposition theorem for integers)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**************************************************************** 
 * Description: c++ prime factor
 * Author: Alex Li
 * Date: 2023-06-12 18:13:30
 * LastEditTime: 2023-07-02 16:35:57
****************************************************************/
#include <iostream>
using namespace std;
 
void primeFactors(int n){
    int c=2;
    while(n>1){
        if(n%c==0){
        cout<<c<<" ";
        n/=c;
        }
        else c++;
    }
}
 
int main(){
    int n;
    cin>>n; 
    primeFactors(n);
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**************************************************************** 
 * Description: C++ implementation of Unique decomposition theorem for integers
 * Author: Alex Li
 * Date: 2023-06-21 10:44:25
 * LastEditTime: 2023-06-21 11:08:12
****************************************************************/
#include <iostream>
using namespace std;

vector<int>v;//存储唯一分解定理的分解值
void dev(int n){
	int c=sqrt(n);//这里要单独提出来，否则下面for循环的时候n会变
	for(int i=2;i<=c;++i){
		//当n整除i的时候，就一直除到这个没办法再除为止
		while(n%i==0)n/=i,v.push_back(i);
		//容易发现，经过这样的处理，绝对不会出来i是非素数的情况下n%i=0,
		//比如i=2的时候被n整除，n除i到没有办法再除以之后，n绝对不可能在之后整除4
    }
    if(n!=1)//可能整除完还剩下一个数字， 这个数字一定是素数
		v.push_back(n);
}

int main(){
    int n;
    cin>>n;
    dev(n);
    for (int i = 0; i <v.size(); i++)cout<<v[i]<<' ';
    
}