Advertisement
momo2345

prime factors

Nov 17th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6. typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
  7. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define endl "\n"
  9. #define mn int main()
  10. #define frac() cout.unsetf(ios::floatfield);cout.precision(6);cout.setf(ios::fixed,ios::floatfield);
  11.  
  12.  
  13.  
  14. const int mx=1e5+123;
  15. bitset<mx>isprime;
  16. vector<int>prime;
  17. void primegen(int n)
  18. {
  19.     n+=10;
  20.     for(int i=3;i<=n;i+=2) isprime[i]=1;
  21.     for(int i=3;i*i<=n;i+=2){
  22.             if(isprime[i]){
  23.         for(int j=i*i;j<=n;j+=(i*2))
  24.             isprime[j]=0;
  25.       }
  26.     } //O(n)
  27.     isprime[2]=1;
  28.     prime.push_back(2);
  29.     for(int i=3;i<=n;i+=2){
  30.         if (isprime[i]) prime.push_back(i);
  31.     }
  32. }
  33.  
  34. vector<long long >factorization(long long n)
  35. {
  36.     vector<long long >ret;
  37.     for(auto p : prime){
  38.         if(1LL*p*p>n) break;
  39.         if(n%p==0){
  40.             while(n%p==0){
  41.                 ret.push_back(p);
  42.                 n/=p;
  43.             }
  44.         }
  45.     }
  46.     if(n>1) ret.push_back(n);
  47.     return ret;
  48. }
  49. mn
  50. {
  51.     suni;
  52.     primegen(1e5);
  53.     long long n;
  54.     while(cin>>n)
  55.     {
  56.         if(n==0) break;
  57.         vector<ll>ans=factorization(abs(n));
  58.         if(n<0){
  59.             reverse(ans.begin(),ans.end());
  60.             ans.push_back(-1);
  61.             reverse(ans.begin(),ans.end());
  62.         }
  63.         cout<<n<<" = "<<ans[0];
  64.         for(ll i=1;i<ans.size();i++) cout<<" x "<<ans[i];
  65.         cout<<endl;
  66.     }
  67.  
  68. }
  69.  
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement