试题基础练习分解质因数-蒲公英云

试题基础练习分解质因数

资源限制
内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
　　求出区间[a,b]中所有整数的质因数分解。
输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
　　先筛出所有素数，然后再分解。
数据规模和约定
　　2<=a<=b<=10000
运行结果：

#include <iostream>
#include <vector>
using namespace std;
// 判断是否是质数
bool IsPrime(int n)
{
    int i;
    for (i = 2; i <= n/2; ++i)
    {
        if (n%i == 0)
        {
            return false;
        }
    }
    if (i > n/2)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    vector<int> v; // 存储2-b的所有质数
    int a,b;  
    cin >> a;
    cin >> b;
    for (int i = 2; i<=b; ++i) // 存储质数过程
    {
        if (IsPrime(i))
        {
            v.push_back(i);
        }
    }
    for ( int i = a; i <= b; ++i) // 从a开始处理直到b
    {
        if (IsPrime(i))   // 是质数的话 直接输出
        {
            cout << i << "=" << i;
        }
        else  // 不是质数分别处理
        {
            cout << i << "=";
            int temp = i;// 暂存i
            int index = 0; //存储质数的数组下标 索引
            while (temp != 1)  // 当前数字没有被除尽时继续
            {
                if (temp%v[index] == 0)  // 从第一个质数开始除
                {
                    cout << v[index];  
                    temp /= v[index];     
                    index = 0; // 还原   即 继续从第一个质数2开始尝试
                    if (temp != 1)   // 控制 * 的输出
                        cout << "*";
                }
                else  // 不能整除的话尝试下一个质数
                {
                    index++;
                }
            }
        }
        cout << endl;
    }
    return 0;
}