fork download 
  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){
  28.     unordered_map <ll,ll> a2;
  29.     while(vl!=1){
  30.         ll d = spf[vl]; a2[d]++;
  31.         vl = vl/d;
  32.     }
  33.     return a2;
  34. }
  35.  
  36. int main() {
  37.     ll n;
  38.     cin>>n;
  39.     computeSPF();  // Compute SPF for all numbers from 2 to MAXN
  40.     ll b[n+1]={0};
  41.     for(ll i=1;i<=n;i++){
  42.         cin>>b[i];
  43.         unordered_map <ll,ll> a2 = cl(b[i]);
  44.         cout<<"for index i->";
  45.         for(auto itr = a2.begin();itr!=a2.end();++itr){
  46.             cout<<itr->first<<" "<<itr->second;
  47.             cout<<"\n";
  48.         }
  49.  
  50.  
  51.  
  52.     }
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 11156KB
comments (?)
stdin 
3
20 35 17
stdout 
for index i->5 1
2 2
for index i->7 1
5 1
for index i->17 1
https://ideone.com/nkYNdl
language:
C++14 (gcc 8.3)
created:
8 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!