素因子分解

前言

这是一道在pta上的题目，成功地卡了我几个小时……我第一种的解法超时，好不容易写出了第二种复杂的解法终于把题目过了，然后回头一看同学的做法简单多了，顿时感觉我是小丑……好好好，记录一下。

题目

给定某个正整数 N，求其素因子分解结果，即给出其因式分解表达式 N=p1^k1*p2^k2*…*pm^km。

输入格式：

输入long int范围内的正整数 N。

输出格式：

按给定格式输出N的素因式分解表达式，即 N=p1^k1*p2^k2*…*pm^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki为1即因子pi只有一个时不输出ki。

输入样例：

输出样例：

1	1323=3^3*7^2

代码实现

啥也不想解释，代码自己看吧┭┮﹏┭┮

我的小丑做法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct sys {
	LL num;
	LL ans=0;
};

bool operator <(const sys& a, const sys& b) {
	return a.num < b.num;
}

set<sys> arr;

LL n,x=0;

void add(LL num) {
	sys temp;
	temp.num = num, temp.ans = 1;
	set<sys>::iterator ops = arr.lower_bound(temp);
	if (ops == arr.end()) arr.insert(temp);
	else {
		temp.ans += ops->ans;
		arr.erase(ops);
		arr.insert(temp);
	}
}

bool is_prime(LL num) {
	LL temp = sqrt(num);
	for (LL i=2; i <= temp; i++)
		if (num % i == 0) return false;
	return true;
}

int main() {
	cin >> n;
	if (n == 1) {
		cout << "1=1";
		return 0;
	}
	cout << n << "=";

	while (!is_prime(n)) {
		for (LL i=n / 2; i >= 2; i--) {
			if (n % i == 0) {
				LL t = n / i;
				add(t);
				n = i;
				break;
			}
		}
	}
	add(n);
	
	LL flag = 0; // 输出 
	for (set<sys>::iterator it = arr.begin(); it != arr.end(); it++) {
		if (flag) cout << "*"; 
		cout << it->num;
		if (it->ans != 1) cout << "^" << it->ans;
		flag = 1;
	}
	
	return 0;
}

同学优雅的做法

#include <stdio.h>
#define ll long long
int isprime(ll a){
    for(ll i = 2 ; i <= a / i ; i++){
        if(a % i == 0 ) return 0;
    }
    return 1;
}

int ans[10000];
int ans_cnt[10000];

int main(){
    ll N;
    scanf("%lld",&N);
    int is_can = 0;
    ll temp = N;
    
    for(ll i = 2 ; i <= N / i && temp!=1; i++){
        if(!isprime(i)) continue;
        
        //素数因子
        ll cnt = 0;

        if(temp%i==0){
            is_can++;
            ans[is_can] = i;//存符合的素数因子
            while(temp%i==0){
                cnt++;
                temp /= i;
            }
            //printf("!%d!",i);
            ans_cnt[is_can] = cnt;//存素数因子的个数
        }
    }
    
    printf("%lld=",N);
    if(is_can==0) printf("%lld",N);
    
    else for(ll i = 1 ; i <= is_can ; i++){
        
        if(ans_cnt[i]==1) {
            printf("%d",ans[i]);
            //printf("!");     
        }
        else printf("%d^%d",ans[i],ans_cnt[i]);
        
        if(i != is_can) printf("*");
    }
    
}