largestPrimeFactorIsAbove function

bool largestPrimeFactorIsAbove(
  1. int n,
  2. int k
)

Returns whether largestPrimeFactor(n) > k.

This function is significantly more efficient than doing that check explicitly.

Implementation

bool largestPrimeFactorIsAbove(int n, int k) {
  for (int i = 0, p = 2;;) {
    if (p * p > n || p > k) break;
    if (n % p != 0) {
      i += 1;
      p = primes.getPrime(i);
    } else {
      n ~/= p;
    }
  }
  return n > k;
}