Saleh127

uva 583 (prime factor).cpp

Jun 2nd, 2020
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maX 1000000
  4. #define ll long long
  5. bool marked[maX];
  6. vector<ll>factor,prime;
  7. void sieve()
  8. {
  9. for(ll i=3;i*i<=maX;i+=2)
  10. {
  11. if(marked[i]==false)
  12. {
  13. for(ll j=i*i;j<=maX;j+=i+i)
  14. {
  15. marked[j]=true;
  16. }
  17. }
  18. }
  19. prime.push_back(2);
  20. for(ll i=3;i<=maX;i+=2)
  21. {
  22. if(marked[i]==false)
  23. {
  24. prime.push_back(i);
  25. }
  26. }
  27. }
  28.  
  29. void primefactor(ll n)
  30. {
  31. for(ll i=0;prime[i]*prime[i]<=n;i++)
  32. {
  33. if(n%prime[i]==0)
  34. {
  35. while(n%prime[i]==0)
  36. {
  37. n=n/prime[i];
  38. factor.push_back(prime[i]);
  39. }
  40. }
  41. }
  42. if(n>1)
  43. {
  44. factor.push_back(n);
  45. }
  46.  
  47. }
  48.  
  49. int main()
  50. {
  51. sieve();
  52. ll a,c,d,i,j,k;
  53. while(cin>>a)
  54. {
  55. if(a==0) break;
  56. d=abs(a);
  57. printf("%lld = ",a);
  58. primefactor(d);
  59. if(a==1 || a==-1)
  60. {
  61. printf("%lld\n",a);
  62. continue;
  63. }
  64. if(a<0) printf("-1 x ");
  65.  
  66. c=0;
  67. for(i=0;i<factor.size();i++)
  68. {
  69. if(c==0)
  70. {
  71. printf("%lld",factor[i]);
  72. c++;
  73. }
  74. else
  75. {
  76. printf(" x %lld",factor[i]);
  77. }
  78. }
  79. printf("\n");
  80. factor.clear();
  81. }
  82.  
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment