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

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
  求出区间[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

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[10000] = {0}; 
//判断是否为质数 
bool check(int value){
  for(int i=2;i<value;i++)
  if(value%i==0) return true;
  return false;
}
int main()
{
  setnum(); 
  int a,b,ss,len;
  scanf("%d%d",&a,&b);
  for(int i=a;i<=b;i++){
  cout<<i<<"="; 
  ss = i,len=0;
  for(int j=2;j<=ss;j++){
    if(check(j))      //判断是否为质数，是的话返回false 
    continue;
    if(ss%j==0){      //判断是否整除 
    if(len==0)
      cout<<j;
    else
      cout<<"*"<<j;
    len++;     //len表示的是是不是第一个数，不是第一个数就是*2,是的话为2 
    ss = ss/j;
    j--;      //如果找到还要减去1 
    }
  } 
  cout<<endl;
  } 
  return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[10000] = {0}; 
//生成质数数组，存放0或者1，1代表是，0代表不是
void setnum()
{
  for(int i=2;i<=10000;i++){
  for(int j=2;j<i;j++)
    if(i%j==0){
    continue;
    }
  dp[i] = 1;
  }
}
int main()
{
  setnum(); 
  int a,b,ss,len;
  scanf("%d%d",&a,&b);
  for(int i=a;i<=b;i++){
  cout<<i<<"="; 
  ss = i,len=0;
  for(int j=2;j<=ss;j++){
    if(!dp[j])      //判断是否为质数，是的话返回false 
    continue;
    if(ss%j==0){      //判断是否整除 
    if(len==0)
      cout<<j;
    else
      cout<<"*"<<j;
    len++;     //len表示的是是不是第一个数，不是第一个数就是*2,是的话为2 
    ss = ss/j;
    j--;      //如果找到还要减去1 
    }
  } 
  cout<<endl;
  } 
  return 0;
}