质因子分解

概念：所谓质因子分解是将一个正整数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;
}

 

 

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

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

这里说明一下(针对方法二）：
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）的数。