试题 基础练习 分解质因数

试题 基础练习 分解质因数

资源限制 内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：.0s Python时间限制：5.0s 问题描述 　　求出区间[a,b]中所有整数的质因数分解。 输入格式 　　输入两个整数a，b。 输出格式 　　每行输出一个数的分解，形如k=a1a2a…(a1<=a2<=a…，k也是从小到大的)(具体可看样例) 样例输入 10 样例输出 = 4=22 5=5 6=2 7=7 8=222 9= 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;
}