Advertisement
Guest User

Untitled

a guest
May 24th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. int main() {
  7. ios_base::sync_with_stdio(false);
  8. cin.tie(NULL);
  9.  
  10. //600851475143
  11. ll number;
  12. cin >> number;
  13.  
  14. ll root = sqrt(number) + 10;
  15.  
  16. vector<bool> isPrime(root, true);
  17.  
  18. ll answer = 0;
  19. bool hasDivisor = false;
  20.  
  21. for (ll i = 2; i < root; i++) {
  22. if (isPrime[i]) {
  23. for (ll j = i * i; j < root; j += i) {
  24. isPrime[j] = false;
  25. }
  26.  
  27. //cout << i << " isPrime" << endl;
  28.  
  29. //check ok
  30. if (number % i == 0) {
  31. answer = max(answer, i);
  32.  
  33. while (number % i == 0) {
  34. number /= i;
  35. }
  36.  
  37. hasDivisor = true;
  38. }
  39. }
  40. }
  41.  
  42. answer = max(answer, number);
  43.  
  44. cout << (hasDivisor ? answer : number) << endl;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement