Submission

PPPx-PPx--

Score: 50

User: 17458

Problemset: แยกตัวประกอบ

Language: cpp

Time: 0.003 second

Submitted On: 2024-11-20 19:08:34

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

const int MxN = 1e5;

map<int,int> factor;
queue<int> q;
vector<bool> is_prime(MxN,true);
int main() {
    float n; cin >> n;
    //prime
    for (int i = 2;i <= MxN;i++) {
        if (is_prime[i]) {
            for (int j = i + i;j < MxN;j += i) is_prime[j] = false;
        }
    }

    int i = 2;
    while (n > 1) {
        if (is_prime[i]) {
            while (trunc(n / i) == (n/i)) {
                factor[i]++;
                if (factor[i] == 1) q.push(i);
                n /= i;
            }
        }
        i++;
    }

    while (!q.empty()) {
        int num = q.front(); q.pop();
        cout << num << '^' << factor[num] << ' ';
    }
}