给出一个正整数N(2<=N<=2147483647),要求将其分解成质因子的连乘积。(质因子连乘时按从小到大顺序)(注:某一正整数的质因子指能整除该数的质数整数,也称质因数或质约数。 如24的因子有1 、2、3、4、6、8、12、24。其中是质数的是2,3 所以24的质因子就是2,3。) 例如:当N=24时 结果为:24=2*2*2*3 又如:当N=13时 (13的质因子只有13一个) 输出结果为:13=13
输入格式
只有一行,即一个整数N
输出格式
只有一行,按格式输出
输入/输出例子1
输入: 38
输出: 38=2*19
浅说:这个问题本身不难,难点是如何避免超时的问题,我们要把判断质数函数进行优化,分解质因数部分进行优化算法~,好啦,下面请看代码实现~
#include<bits/stdc++.h>
using namespace std;
int m;
bool zhishu(int n) //优化质数函数
{if(n == 2) return true;if(n % 2 == 0) return false;for(int i = 3;i <= sqrt(n);i+=2){if(n%i == 0)return false;}return true;
}int main() {cin >> m; // 输入整数 mcout << m << "="; // 输出格式,例如 "24="if (zhishu(m)) { // 如果 m 是质数,直接输出 mcout << m;return 0;}for (int i = 2; i <= m; i++) { // 从 2 开始尝试分解质因数if (m % i == 0) { // 如果 i 是 m 的因子while (m % i == 0) { // 完全筛去 i 因子if (i != m) cout << i << "*"; // 输出因子 im /= i; // 更新 m 的值}}if (zhishu(m)) { // 如果剩下的 m 是质数,直接输出cout << m;return 0;}}return 0;
}
创造不易,如果对您有所帮助,请一键三连哦~你的支持是我继续创造的动力源泉~