蓝桥杯 试题 基础练习 分解质因数

问题描述

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

输入格式

　　输入两个整数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<=a<=b<=10000

解题思路：

先筛选出质数，这个简单，难点在于如何对素数因式分解。

素数的因式一定都是质数，所有可以直接在质数里面找一个素数的因式。首先需要打印出质数表，我打印了前1000个质数，够用了。然后需要找到这个素数的因式里面最小的数。比例9的因式最小的数是3，25的因式最小的数是5。先输出，然后在遍历质数表，从小到大找到所有的能整除素数的质数。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
#include<cmath>
using namespace std;
const int N=1000; 
int zs[N+2]={};
int zhishu(int a){//判断是否是质数 
  if(a==1)
    return 1;
  for(int i=2;i<=sqrt(a);i++)
    if(a%i==0)
      return 0;
  return 1;
}
int printZS(){
  for(int i=2,j=0;i<10000;i++)
    if(zhishu(i))
      zs[j++]=i;
}

void f(int a){
  for(int i=0;i<N;i++)
    while(a%zs[i]==0)
    {
      cout<<"*"<<zs[i];
      a/=zs[i];
    }
  cout<<endl;
}
int main(){
  int m,n;
  cin>>m>>n; 
  printZS();//打印质数表 
  for(int i=m;i<=n;i++)
  {
    if(zhishu(i))//是质数就直接输出 
      cout<<i<<"="<<i<<endl;
    else{//是素数 
      cout<<i<<"=";//先输出格式 
      for(int j=0;j<N;j++)//找到素数的因式最小的数，然后输出 
        if(i%zs[j]==0) 
        {
          cout<<zs[j];
          f(i/zs[j]);
          break;//一定要跳出循环，因为素数的因式最小的数是唯一的 
        }     
    }
  }
}