蓝桥杯 ADV-223 因式分解

因式分解"/>

蓝桥杯 ADV-223 因式分解

蓝桥杯 ADV-223 因式分解

问题描述

设计算法，用户输入合数，程序输出若个素数的乘积。例如，输入6，输出2*3。输入20，输出2*2*5。
输入样例
120
输出样例
2*2*2*3*5

思路解析

• 筛选出5000内的素数，从头到尾进行取余，余数为0，则该素数为因子，余数不为0，则迭代至下一个素数，直到该数为1。

#include<iostream>
#include<vector>using namespace std;bool isPrime(int num){if (num == 0 || num == 1)return false;for (int i = 2; i * i <= num; i++){if (num % i == 0)return false;}return true; 
}int main() {int cn, index = 0;vector<int> pm, res;cin >> cn;for (int i = 0; i < 50000; i++){if (isPrime(i)){pm.push_back(i);}}index = 0;while (cn != 1){if (cn % pm[index] == 0){cn /= pm[index];res.push_back(pm[index]);}elseindex++;        }cout << res[0];for (int i = 1; i < res.size(); i++){cout << "*";cout << res[i];}return 0;
}