质因子分解

男娘i 2022-04-24 08:48 230阅读 0赞

概念：所谓质因子分解是将一个正整数n写成一个或多个质数的乘积形式。  
例如：6=2\*3，180=2\*2\*3\*3\*5，也可以写成指数形式，例如 180=2^2\*3^2\*5^1；  
你会发现最终会归结到若干个不同**素数(质数)的乘积**。

注意：由于1本身不是素数，因此它没有质因子，下面针对大于1的正整数来说。

这里提供2种质因子分解的代码，可根据要求选择，**重点讲解方法(二）**。  
**方法(一)：**

#include <stdio.h>
    int main(){
        int n;  // 用户输入的整数
        int i;  // 循环标志
        printf("输入一个整数：");
        scanf("%d",&n);
        printf("%d=",n);
        // n>=2才执行下面的循环
        for(i=2; i<=n; i++){
            while(n!=i){
                if(n%i==0){
                    printf("%d*",i);
                    n=n/i;
                }else
                    break;
            }
        }
        printf("%d\n",n);
        return 0;
    }

![20190420200237138.png][]

**方法(二) ：指数形式输出**

#include <stdio.h>
    #include <math.h>
    const int maxn=100001;
    //判断是否为素数
    bool is_prime(int n){  
    	if(n==1) return false;
    	int sqr=(int)sqrt(1.0*n);
    	for(int i=2;i<=sqr;i++){
    		if(n%i==0) return false;
    	}
    	return true;
    }
    int prime[maxn],pNum=0;
    //构建素数表 
    void Find_prime(){
    	for(int i=1;i<maxn;i++){
    		if(is_prime(i)==true){
    			prime[pNum++]=i;
    		}
    	}
    }
    
    //存放质因子和个数
    struct factor{
    	int x,count;
    }f[10]; //连乘即将超越int上限 
    int main(){
    	Find_prime();
    	int n;
    	int num=0;//记录质因数个数
    	scanf("%d",&n);
    	if(n==1) printf("1=1");//特殊判断
    	else{
    		printf("%d=",n);
    		int sqr=(int)sqrt(1.0*n);
    		//枚举根号n以内的质因数
    		for(int i=0;i<pNum&&prime[i]<=sqr;i++){
    			if(n%prime[i]==0){
    				f[num].x=prime[i];
    				f[num].count=0;
    				while(n%prime[i]==0){
    					f[num].count++;
    					n/=prime[i];
    				}
    				num++;
    			}
    			if(n==1){
    				break;
    			}
    		} 
    		//如果最终除不尽，则一定有且仅有一个大于根号n的质因子。 
    		if(n!=1){
    			f[num].x=n;
    			f[num++].count=1;
    		}
    
    		//打印
    		for(int i=0;i<num;i++){
    			if(i>0) printf("*");
    			printf("%d",f[i].x);
    			if(f[i].count>1){
    				printf("^%d",f[i].count);
    			}
    		} 
    	}
    	return 0; 
    }

![2019042020011028.png][]  
这里说明一下(针对方法二）：  
1）考虑到2\*3\*5\*7\*11\*13\*17\*19\*23\*29就已经超出了int范围，所以只需要将 f 数组开到10就可以了。  
2）时间复杂度为O（√n）。

**核心思路:  
对于正整数n来说，如果它存在1和本身之外的因子，那么一定是在sqrt(n）的左右成对出现（或者就等于sqrt(n)^2）。  
推广到“质因子”上面，会得到一个强化结论：  
情况1.所有质因子≤sqrt(n）.  
情况2.一个质因子>sqrt(n)，其余全部≤sqrt(n）。 在上述代码中，最后除不尽（不为1）则有且仅有一个大于sqrt（n）的数。**

[20190420200237138.png]: /images/20220217/c05065e4ec6548e883613df120f8e7dc.png
[2019042020011028.png]: /images/20220217/5cf7a5cb1ff34a97a19e9c42902465ad.png