Submission #117045

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define pb push_back
#define mp make_pair
typedef long long ll;
const int inf = (1<<28);

vector<ll> ps;
void sieve(int n) {
  ps = vector<ll>(n);
  rep(i, n) ps[i] = i;
  ps[0] = ps[1] = 0;
  for(int i=2; i*i<=n; i++)
    if(ps[i])
      for(int j=i*i; j<n; j+=i)
        ps[j] = 0;
  ps.erase(remove(all(ps), 0), ps.end());
}

int main() {
  sieve(100000);
  
  ll n;
  while(cin >> n, n) {
    ll ans = -1;
    
    rep(i, ps.size()) {
      if(n % ps[i] == 0) ans = ps[i];
      while(n % ps[i] == 0) n /= ps[i];
    }
    
    if(n != 1) ans = n;
    
    cout << ans << endl;
  }
}

Submission Info

Judge Result