SRM529 Div2 Hard

1000
ここを見る

class MinskyMysteryDiv2 {
public:
  long long computeAnswer(long long N) 
  {
    if (N == 0) return -1;

    const int P = 1000000;    
    bool prime[P];

    fill(prime, prime + P, true);
    prime[0] = prime[1] = false;

    for (lli i = 2; i * i < P; ++i) {
      for (lli j = 2; i * j < P; ++j) {
        prime[i * j] = false;
      }
    }       

    lli mn = 9999999999991LL;
    lli M = N;
    for (lli i = 1; i < P; ++i) {
      if (prime[i]) {
        while (M % i == 0) {
          mn = min(mn, i);
          M /= i;
        }
      }
    }
    if (M != 1LL) mn = min(mn, M);

    lli mx = 1;
    for (lli i = 2; i * i <= N; ++i) {
      if (N % i == 0) {
        mx = max(mx, i);
        mx = max(mx, N / i);
      }
    }

    lli res = mn + mx;
    return res < 9999999999991LL ? res : -1;
  }

};