611
大眾點評筆試算法之質因數分解
將一個正整數分解質因數。例如：輸入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;
}
程序實現效果為：
最後更新：2017-04-03 15:21:51