fork(22) download
copy 
  1. #include <iostream>
  2. #include<vector>
  3.  
  4. using namespace std;
  5.  
  6. #define maxn 10000007
  7.  
  8. vector<int>Primes(maxn);
  9. void least_prime_factor()
  10.  {
  11.  
  12.     Primes[1]=1;
  13. 					for(int i=2;i<=maxn;i++)
  14. 					{
  15. 						Primes[i]=i;
  16. 					}
  17. 					for(int i=4;i<=maxn;i+=2)
  18. 					{
  19. 						Primes[i]=2;
  20. 					}
  21. 					for(int i=3;i*i<=maxn;i++)
  22. 					{
  23. 						if(Primes[i]==i)
  24. 						{
  25. 							for(int j=i*i;j<=maxn;j+=2*i)
  26. 							{
  27. 								if(Primes[j]==j)
  28. 								   Primes[j]=i;
  29. 							}
  30. 						}
  31. 					}
  32.  
  33.  }
  34. vector<int>factorise(int x)
  35. {
  36.     vector<int>ret;
  37.     while(x!=1)
  38.     {
  39.         ret.push_back(Primes[x]);
  40.         x=x/Primes[x];
  41.     }
  42. return ret;
  43. }
  44.  
  45. int main() {
  46.  
  47.  
  48. least_prime_factor();
  49. int n;
  50. while(scanf("%d", &n) == 1)
  51. if(n==1)
  52. {
  53.     printf("1\n");
  54. }
  55. else{
  56.  
  57.     vector<int>ans=factorise(n);
  58.     printf("1 x");
  59.     for(int i=0;i<ans.size();i++)
  60.     {
  61.         if(i==ans.size()-1)
  62.             printf(" %d ", ans[i]);
  63.         else
  64.             printf(" %d x", ans[i]);
  65.     }
  66.     cout<<endl;
  67. }
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0.07s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4JlHQE
language:
C++14 (gcc 8.3)
created:
6 years 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!