什么是分解质因数
质因子分解:将一个正整数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~sqrt(n)范围内的所有质因子p(建一个素数表list),判断 p是否是n的因子(能否整除)
① 如果是,那么给ans结果数组中增加p,并初始化其个数为0。然后,只要p还是n的因子,就不断n除以p,每次操作令p的个数加1,直到p不是n的因子为止
② 如果不是,直接跳过 - 如果在上面的步骤结束后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()