fork download
copy 
  1. #include<iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6.  
  7. void seive(int r, vector<int> &spf) {
  8.     vector<int> arr(r + 1, 1);
  9.     spf.resize(r + 1);
  10.  
  11.     for (int i = 0; i <= r; i++) {
  12.         spf[i] = i;
  13.     }
  14.  
  15.     for (int i = 2; i <= r; i++) {
  16.         if (arr[i] == 1) {
  17.             ll j = (ll)i * i;
  18.  
  19.             while (j <= r) {
  20.                 if (spf[j] == j) {
  21.                     spf[j] = i;
  22.                 }
  23.  
  24.                 arr[j] = 0;
  25.                 j += i;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. unordered_map<ll, ll> factors(ll v, vector<int> &spf) {
  32.     unordered_map<ll, ll> mpp;
  33.  
  34.     while (v != 1) {
  35.         ll a = spf[v];
  36.         mpp[a]++;
  37.         v = v / a;
  38.     }
  39.  
  40.     return mpp;
  41. }
  42.  
  43. int main() {
  44.     int r;
  45.     cin >> r;
  46.  
  47.     vector<int> spf;
  48.     seive(r, spf);
  49.  
  50.     ll v;
  51.     cin >> v;
  52.  
  53.     unordered_map<ll, ll> mpp = factors(v, spf);
  54.  
  55.     for (auto it : mpp) {
  56.         cout << it.first << "^" << it.second << " ";
  57.     }
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
50 10
stdout
copy 
5^1 2^1
https://ideone.com/ZhYrhm
language:
C++14 (gcc 8.3)
created:
12 days 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!