大众点评笔试算法之质因数分解

将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。

代码为：

// 质因数.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<cmath>
#include<cstdlib>
#include<iostream>
using namespace std;

void Analyse(int n)
{
	//打印出
	int i;
	for(i = 2;i <= sqrt(static_cast<double>(n));i++)
	{
		if(n % i == 0)
		{
			n = n/i;
			cout<<i<<"*";
			i--;
		}
	}
	cout<<n<<endl;

}
int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	cin>>n;
	cout<<n<<" = ";
	Analyse(n);
	return 0;
}

程序执行结果为

博客上看到另一种解法，感觉思路很好，其思路为：

对n进行分解质因数,应先找到一个最小得质数k，然后按下述步骤完成： 
（1）如果这个质数恰等于n,则说明分解质因数得过程已经结束,打印出即可. 
（2）如果n>=k，但n能被k整除，则应打印出k的值，并用n除以k得商，作为新的正整数n，重复执行第一步。 
（3）如果n不能被k整除，则用k+1作为k的值，重复执行第一步 

实现代码为：

// 质因数.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<cmath>
#include<cstdlib>
#include<iostream>
using namespace std;

void Analyse(int n)
{
	//首先输出等式左边部分
	cout<<n<<" = ";

	//对n进行质因数分解，应先找到一个最小的质数2
	//如果这个质数恰好等于2，则说明分解质因素的过程结束，打印
	if(n == 2)
	{
		cout<<n<<endl;
	}
	//n小于2时，无法进行质因素分解，提示相应信息
	else if(n < 2)
	{
		cout<<"该数不可以分解质因素"<<endl;
	}
	else
	{
		//如果n>=k,但n能被k整数，则打印出k的值
		for(int i = 2;i <= sqrt(static_cast<double>(n));i++)
		{
			if(n % i == 0)
			{
				n = n/i;
				cout<<i<<"*";
				//重复执行上一步
				i--;
			}
			//cout<<n<<endl;
		}
		cout<<n<<endl;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	cin>>n;
	//cout<<n<<endl;
	Analyse(n);
	return 0;
}

程序实现效果为：