[PAT A1059]Prime Factors
题目描述
输入格式
Each input file contains one test case which gives a positive integer N in the range of long int.
输出格式
输入样例
97532468
输出样例
97532468=2^211171011291
解析
这道题目属于数学题，最主要就是掌握素数的计算就可以了
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
bool isPrime(int n)
{
if (n <= 1) return false;for (int i = 2; i*i <= n; i++) {
if (n%i == 0) return false;}return true;
}
struct factor //记录质因子的数组，由于2*3*5*7*9*11*13*17*19*21>int范围，所以开到10就足够了
{
int x,cnt;
}fac[10];
int main()
{
vector<int> prime;int n;scanf("%d", &n);printf("%d=", n);if (n == 1) printf("%d", n);//特判为1的情况，一开始第四组数据过不了，printf("1=1")过了//，通过这种方法可以猜有没有特定数据在测试数据中，大家也可以使用这种方法“投机取巧”（骗分）,平常练习时不提倡else {
for (int i = 2; i*i <= n; i++) {
if (isPrime(i)) prime.push_back(i);} //首先取0到根号n的素数表，根据计算可以得知，要么所有质因子都在这个范围，要么只有一个大于根号n的质因子（因为如果有两个大于根号n的质因子，那么他们的乘积就已经大于n了）int pNum = 0;for (int i = 0; i < prime.size(); i++) {
if (n%prime[i] == 0) {
fac[pNum].x = prime[i];fac[pNum].cnt = 0;while (n%prime[i] == 0) {
n /= prime[i];fac[pNum].cnt++;}pNum++;}}if (n != 1) {
fac[pNum].x = n;fac[pNum].cnt = 1;}//如果在小于等于根号n里面没找到，那么剩下的就是另一个大于根号n的质因子else pNum--;for (int i = 0; i <= pNum; i++) {
if (fac[i].cnt == 1) printf("%d", fac[i].x);else printf("%d^%d", fac[i].x, fac[i].cnt);if (i != pNum) printf("*");}}return 0;
}