Advertisement
momo2345

largest prime

Nov 17th, 2020
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 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=1e7+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(1e7);
  53. long long n;
  54. while(cin>>n)
  55. {
  56. if(n==0) break;
  57. vector<ll>ans=factorization(abs(n));
  58. if(ans.size()== 1) cout<<-1<<endl;
  59. else cout<<ans[ans.size()-1]<<endl;
  60. }
  61.  
  62. }
  63.  
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement