如何优化适用于Long类型的properFractions函数解决Codewars大数问题？

First off, let's clarify: the number of proper fractions with denominator d is exactly Euler's Totient Function φ(d)—which counts integers from 1 to d-1 that are coprime with d. Your current approaches are missing key optimizations for large values of d, so let's break down the issues and fix them.

Why Your Current Code Fails for Large n #

Let's go through each of your implementations to see the bottlenecks:

• properFractions1: You're on the right track using the totient formula, but looping from 2 to n is catastrophic for large n (like 4e9)—that's billions of iterations. Plus, your isPrime function checks up to sqrt(n) for every i, which adds unnecessary overhead.
• properFractions2/3/4: These all brute-force check every number from 1 to n-1 with GCD. For n=4e9, this means 4 billion operations—way too slow for any time limit.

Key Optimization Techniques #

1. Efficient Prime Factorization (The Core Fix) #

The totient function formula relies on finding the distinct prime factors of n, not checking every number up to n. The formula is:

φ(n) = n × product of (1 - 1/p) for every distinct prime p dividing n

To compute this efficiently, we only need to factorize n up to sqrt(n)—any remaining value greater than 1 after that is a prime factor itself.

Here's a fast, tail-recursive prime factorization function for Scala:

import scala.annotation.tailrec

@tailrec
private def getDistinctPrimeFactors(n: Long, current: Long = 2, factors: Set[Long] = Set.empty): Set[Long] = {
  if (current * current > n) {
    // If remaining n is >1, it's a prime factor
    if (n > 1) factors + n else factors
  } else if (n % current == 0) {
    // Add current to factors, then divide n by current until it's no longer divisible
    getDistinctPrimeFactors(n / current, current, factors + current)
  } else {
    // Skip even numbers after checking 2
    val next = if (current == 2) 3 else current + 2
    getDistinctPrimeFactors(n, next, factors)
  }
}

2. Use Integer Arithmetic to Avoid Precision Loss #

Your properFractions1 uses floating-point multiplication (product * (1.0-1.0/i)), which can lose precision for large n. Instead, rewrite the formula using integer operations:

product = product / p * (p - 1)

Since p is a factor of the current product, division will always be exact—no floating-point errors.

3. Implement the Optimized Totient Function #

Combine the factorization with the integer-based formula:

def properFractionsOptimized(n: Long): Long = {
  if (n == 1) 0L
  else {
    val primeFactors = getDistinctPrimeFactors(n)
    primeFactors.foldLeft(n) { (acc, p) =>
      acc / p * (p - 1)
    }
  }
}

4. Optional: Precompute Small Cases (Minor Speedup) #

You can keep your boundary checks for small n (like n=1, n=2) to skip factorization entirely, but even without them, the optimized function will handle these cases quickly.

Testing the Optimized Code #

• properFractionsOptimized(15) returns 8 (correct, as your original code does)
• For n=4665289405L, the factorization will run in O(sqrt(n)) time (~63k iterations), which is trivial for modern CPUs—no more timeouts.

Final Notes #

The key insight here is recognizing that this problem is just asking for Euler's Totient Function, and the only way to handle large values is to leverage efficient prime factorization instead of brute-force checks. This reduces the time complexity from O(n) to O(sqrt(n)), which is night-and-day for large inputs.

内容的提问来源于stack exchange，提问作者Timothy Anderson