fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int N = 1e6;
  5. vector<ll>spf(N+1,1);
  6.  
  7. void computeSPF(){
  8. 	for(ll i=2;i<=N;i++){
  9. 		spf[i] = i;
  10. 	}
  11.  
  12. 	for(ll i=2;i*i<=N;i++){
  13. 		if(spf[i]==i){  // means it a prime
  14. 			ll start = i*i;
  15. 			for(ll j=start;j<=N;j+=i){
  16. 				spf[j] = i;
  17. 			}
  18. 		}
  19. 	}
  20. }
  21.  
  22. unordered_map<ll,ll> calculatePrimeFactors(ll n){
  23. 	unordered_map<ll,ll>a;
  24. 	while(n!=1){
  25. 		a[spf[n]]++;
  26. 		n = n/spf[n];
  27. 	}
  28. 	return a;
  29. }
  30.  
  31. int main() {
  32. 	ll n;
  33. 	cin>>n;
  34. 	computeSPF();
  35. 	unordered_map<ll,ll>a = calculatePrimeFactors(n);
  36. 	for(auto x:a){
  37. 		cout<<x.first<<" : "<<x.second<<endl;
  38. 	}
  39. 	return 0;
  40. }
Success #stdin #stdout 0.01s 11164KB
comments (?)
stdin
copy 
568
stdout
copy 
71 : 1
2 : 3
https://ideone.com/FOrn0e
language:
C++ (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!