fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. vector<int> spf(1000001);
  5.  
  6. void solve(ll y){
  7.     unordered_map<ll, ll> mp;
  8.     while(y != 1){
  9.         ll d = spf[y];
  10.         mp[d]++;
  11.         y = y / d;
  12.     }
  13.     for(auto it : mp){
  14.         cout << it.first << "^" << it.second << "\n";
  15.     }
  16. }
  17.  
  18. int main() {
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(NULL);
  21.  
  22.     for(int i = 0; i < spf.size(); i++)
  23.         spf[i] = i;
  24.  
  25.     for(int p = 2; p * p < spf.size(); p++){
  26.         if(spf[p] == p){
  27.             for(int i = p * p; i < spf.size(); i += p){
  28.                 if(spf[i] == i) spf[i] = p;
  29.             }
  30.         }
  31.     }
  32.  
  33.     ll n;
  34.     cin >> n;
  35.     vector<ll> arr(n);
  36.     for(ll i = 0; i < n; i++){
  37.         cin >> arr[i];
  38.     }
  39.     for(ll i = 0; i < n; i++)
  40.         solve(arr[i]);
  41.  
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 7068KB
comments (?)
stdin
copy 
2
999983 999999
stdout
copy 
999983^1
11^1
13^1
3^3
37^1
7^1
https://ideone.com/KhK81w
language:
C++ (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!