fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. const ll MAXN = 1000000;
  6.  
  7. vector<ll> spf(MAXN + 1); // spf[i] will store the smallest prime factor of i
  8.  
  9. void computeSPF() {
  10.     // Initialize spf for every number to itself
  11.     for (ll i = 2; i <= MAXN; i++) {
  12.         spf[i] = i;
  13.     }
  14.  
  15.     // Start the sieve process
  16.     for (ll i = 2; i * i <= MAXN; i++) {
  17.         if (spf[i] == i) { // Check if i is prime
  18.             for (ll j = i * i; j <= MAXN; j += i) {
  19.                 if (spf[j] == j) { // Update spf[j] to the smallest prime factor
  20.                     spf[j] = i;
  21.                 }
  22.             }
  23.         }
  24.     }
  25. }
  26.  
  27. unordered_map <ll,ll> cl(ll vl){ unordered_map <ll,ll> a2;
  28.     while(vl!=1){
  29.         ll d = spf[vl]; a2[d]++;
  30.         vl = vl/d;
  31.     }
  32.     return a2;
  33. }
  34.  
  35. int main() {ll n;cin>>n;
  36.     // Compute SPF for all numbers from 2 to MAXN
  37.     computeSPF();
  38.     ll b[n+1]={0};
  39.     for(ll i=1;i<=n;i++){
  40.         cin>>b[i];
  41.         unordered_map <ll,ll> a2 = cl(b[i]);
  42.         cout<<"for index i->";
  43.         for(auto itr = a2.begin();itr!=a2.end();++itr){
  44.             cout<<itr->first<<" "<<itr->second;
  45.             cout<<"\n";
  46.         }
  47.  
  48.  
  49.  
  50.     }
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.02s 11112KB
comments (?)
stdin
copy 
5

10 121 50 100 49
stdout
copy 
for index i->5 1
2 1
for index i->11 2
for index i->5 2
2 1
for index i->5 2
2 2
for index i->7 2
https://ideone.com/j0E05A
language:
C++ (gcc 8.3)
created:
1 day 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!