博客

什么是分解质因数

质因子分解：将一个正整数n写成一个或多个质数的乘积的形式。

思路

求出区间[a,b]中所有整数的质因数分解。

每行输出一个数的分解，形如k=a1

a2

a3…(a1<=a2<=a3…，k也是从小到大的)

样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

先筛出所有素数，构建

素数表

，然后再分解。

素数的判断

：如果在2~n-1之间存在n的约数，设为k，即n%k = 0，那么k*(n/k) = n，即n/k也为n的一个约数，且k与n/k中一定满足其中一个≤sqrt(n)，另一个≥sqrt(n)【sqrt(n)为根号n】。所以只要判定n能否被2,3，…，|sqrt(n)|中的一个数整除，即可判定n是否为素数

对于一个正整数n来说，如果他存在1和本身之外的因子，那么一定是在sqrt(n)左右成对出现。因此，对于正整数n来说，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只存在一个大于sqrt(n)的质因子，其他全部小于等于sqrt(n)。

分解质因数

：

1. 枚举1~sqrt(n)范围内的所有质因子p（建一个素数表list），判断 p是否是n的因子（能否整除）
   
   ① 如果是，那么给ans结果数组中增加p，并初始化其个数为0。然后，只要p还是n的因子，就不断n除以p，每次操作令p的个数加1，直到p不是n的因子为止
   
   ② 如果不是，直接跳过
2. 如果在上面的步骤结束后n仍然＞1，说明n有且仅有一个大于sqrt(n)的质因子，这时需要把这个质因子加入ans结果数组，令其个数为1

至此，ans数组中存放的就是质因子分解的结果。

python可以用字典表示 {质因子：个数}

C++可以使用结构体：

定义结构体factor用来存放质因子及其个数。

struct factor{
	int x, cnt; //x为质因子，cnt为其个数
}fac[10];

由于2×3×5×7×11×13×17×19×23×29就已经超过了int范围，所以对int型的数来说数组大小只需要开到10就可以了。

C++

给出一个int范围的整数，按照从小到大的顺序输出其分解为质因数的乘法算式。

例如97532468 = 2^2

11

17

101

1291

#include<bits/stdc++.h>
using namespace std;
const int maxn =100010;
int prime[maxn],pNum = 0;//prime为素数表 
bool p[maxn] = {false};
void Find_Prime(){ //构建素数表 
	for(int i =2;i<maxn;i++){
		if(p[i] == false){
			prime[pNum++] = i;
			for(int j=i+i;j<maxn;j+=i){
				p[j] = true;
			}
		}
	}
}

struct factor{
	int x,cnt;
}fac[10];

int main(){
	Find_Prime(); //创建素数表 
	int n,num=0;//num为n的不同质因子的个数
	scanf("%d",&n);
	if(n==1) printf("1=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){//如果prime[i]是n的因子 
				fac[num].x = prime[i];//记录质因子 
				fac[num].cnt = 0;
				while(n%prime[i] == 0){//计算出质因子prime[i]的个数 
					fac[num].cnt ++;
					n /= prime[i];
				}
				num++;//不同质因子个数加一 
			}
			if(n==1) break; //及时退出循环，节省时间 
		}
		if(n != 1){//还有一个大于根号n的质因子 
			fac[num].x = n;
			fac[num++].cnt = 1;
		}
		//按格式输出结果 
		for(int i =0;i<num;i++){
			if(i>0)printf("*");
			printf("%d",fac[i].x);
			if(fac[i].cnt >1){
				printf("^%d",fac[i].cnt);
			}
		} 
	} 
	return 0;
} 

Python

import math
a,b = map(int,input().split( )) #输入ab两个整数区间

def isPrime(num): #判断是否是素数
    flag = 1
    sqrtn = int(math.sqrt(num))  #计算根号n
    for i in range(2,sqrtn+1):  #遍历2~根号n
        if(num%i == 0):
            flag = 0  #不是素数
            break
    return flag
    
for i in range(a,b+1): #打印i = 分解质因数
    print("%d="%i,end="")
    if isPrime(i) == 1:#i是素数
        print(i) #素数的质因子只有自己
    else: #i不是素数
        leap_table=[] #素数表
        sqr = int(math.sqrt(i)) 
        for j in range(2,sqr+1): #将2~根号i之间的素数加入素数表
            if isPrime(j):
                leap_table.append(j)    
        ans=[] #i的所有分解的质因子
        Fresult={} #{质因子：质因子出现的次数}
        for j in leap_table: #遍历i的素数表
            if i % j ==0: #j是i的质因子
                ans.append(j)
                Fresult[j] = 0  #质因子j出现次数初始化为0
                while(i%j==0): #循环多次查找i可以分解为多少个质因子j
                    Fresult[j] +=1 
                    i= i//j #分解质因子j后的new_i
            if i==1:	#i变为1，无法再进行分解
                break
        if i != 1: #遍历结束i不为1，则有且仅有一个＞根号n的质因子
            ans.append(i)
            Fresult[i] = 1
        for k in range(len(ans)): #按格式打印分解后的所有的质因数
            if k >0 :
                print("*",end="")
            if (Fresult[ans[k]] == 1):
                print(ans[k],end="")
            else:
                while Fresult[ans[k]]:
                    print(ans[k],end="")
                    Fresult[ans[k]] -= 1
                    if(Fresult[ans[k]] > 0):
                        print("*",end="")
        print()