试题 基础练习 分解质因数

#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;
}