大众点评笔试算法之质因数分解
将一个正整数分解质因数。例如：输入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的值，重复执行第一步