fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1000000;
  5. vector<long long> res;
  6.  
  7. void spf() {
  8.     res.resize(MAXN + 1);
  9.  
  10.     for (int i = 2; i <= MAXN; i++) {
  11.         res[i] = i;
  12.     }
  13.  
  14.     for (int i = 2; i * i <= MAXN; i++) {
  15.         if (res[i] == i) {
  16.             for (int j = i * i; j <= MAXN; j += i) {
  17.                 if (res[j] == j) {
  18.                     res[j] = i;
  19.                 }
  20.             }
  21.         }
  22.     }
  23. }
  24.  
  25. unordered_map<long long,long long> helper_fn(long long n) {
  26.     unordered_map<long long,long long> mpp;
  27.  
  28.     while (n != 1) {
  29.         long long d = res[n];
  30.         mpp[d]++;
  31.         n /= d;
  32.     }
  33.     return mpp;
  34. }
  35.  
  36. int main() {
  37.     spf();
  38.  
  39.     int n;
  40.     cin >> n;
  41.     vector<int> nums(n);
  42.  
  43.     for (int i = 0; i < n; i++) {
  44.         cin >> nums[i];
  45.         auto mpp = helper_fn(nums[i]);
  46.         for (auto it : mpp) {
  47.             cout << it.first << "^" << it.second << " ";
  48.         }
  49.     	cout<<endl;
  50.     }
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.02s 11108KB
comments (?)
stdin 
4
45 31 67 65
stdout 
5^1 3^2 
31^1 
67^1 
13^1 5^1
https://ideone.com/i5gyy5
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!