Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- //600851475143
- ll number;
- cin >> number;
- ll root = sqrt(number) + 10;
- vector<bool> isPrime(root, true);
- ll answer = 0;
- bool hasDivisor = false;
- for (ll i = 2; i < root; i++) {
- if (isPrime[i]) {
- for (ll j = i * i; j < root; j += i) {
- isPrime[j] = false;
- }
- //cout << i << " isPrime" << endl;
- //check ok
- if (number % i == 0) {
- answer = max(answer, i);
- while (number % i == 0) {
- number /= i;
- }
- hasDivisor = true;
- }
- }
- }
- answer = max(answer, number);
- cout << (hasDivisor ? answer : number) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement