质因子分解-蒲公英云

质因子分解

男娘i 2022-04-24 08:48 362阅读 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;
}

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

#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）的数。