求给定质因数分解算法的时间复杂度及时间优化方案

Let's break down the time complexity of your prime factorization code step by step, then dive into optimizations focused solely on improving runtime efficiency.

First, here's your code formatted for readability:

function primes(n) { 
  let primeNumbers = [2]; 
  if (n < 2) { return []; } 
  else if (n == 2) { return [2]; } 
  for (let i = 3; i <= n; i++) { 
    let x = i; 
    let j = 0; 
    let isPrime = true; 
    while (j < primeNumbers.length && primeNumbers[j] <= Math.sqrt(i)) { 
      if (x % primeNumbers[j] == 0) { 
        isPrime = false; 
        break; 
      } else { 
        j++; 
      } 
    } 
    if (isPrime) { 
      primeNumbers.push(x); 
    } 
  } 
  return primeNumbers; 
}

function primeFactors(n) { 
  let primeNumbers = primes(Math.sqrt(n)); 
  let i = 0; 
  let x = n; 
  if (n == 1) { return [1]; } 
  if (n == 2) { return [2]; } 
  let primeFactors = []; 
  while (i < primeNumbers.length) { 
    while (x % primeNumbers[i] == 0) { 
      primeFactors.push(primeNumbers[i]) 
      x = x / primeNumbers[i]; 
      if (x == 1) { break; } 
    } 
    if (x == 1) { break; } 
    i++; 
  } 
  if (x > 2) { 
    primeFactors.push(x); 
  } 
  return primeFactors; 
}

console.log("test : " + primes(122));

Time Complexity Analysis #

1. primes(n) Function #

This function uses trial division to generate primes up to n. Here's the breakdown:

• The outer loop runs from 3 to n, so that's roughly O(n) iterations.
• For each number i, the inner while loop checks divisibility against primes up to sqrt(i). For prime i, this loop runs until we've checked all primes smaller than sqrt(i). By the prime number theorem, the number of primes less than sqrt(i) is about sqrt(i)/ln(sqrt(i)).
• Combining these, the overall time complexity is O(n * sqrt(n)/ln(n)), which simplifies to O(n^(3/2)/ln(n)). The ln(n) term softens the growth, but the dominant factor is the n^(3/2) term—this gets slow quickly for large n.

2. primeFactors(n) Function #

This function relies on primes(Math.sqrt(n)) to get primes for factorization:

• The primes(Math.sqrt(n)) call dominates the runtime here, with a time complexity of O( (sqrt(n))^(3/2)/ln(sqrt(n)) ) = O(n^(3/4)/ln(n)).
• The subsequent loops for dividing n by primes are negligible in comparison—they run in O(sqrt(n)/ln(n)) time at worst, which is much slower than the prime generation step.
• So overall, primeFactors(n) has a time complexity of O(n^(3/4)/ln(n)).

Optimizations (Time Complexity Focused) #

These changes will drastically reduce runtime, with no regard for space complexity or coding style:

• Replace trial division with the Sieve of Eratosthenes for prime generation:

  • The Sieve of Eratosthenes generates all primes up to n in O(n log log n) time—this is way faster than your current trial division approach for large n. For example, generating primes up to 1e6 with the sieve is orders of magnitude quicker than trial division.
  • When using the sieve for primes(Math.sqrt(n)), the prime generation step drops to O(sqrt(n) log log sqrt(n)), making primeFactors(n)'s overall complexity O(sqrt(n) log log n)—a huge improvement.

• Tweak trial division (if you stick with it):

  • Skip even numbers after 2: Increment i by 2 instead of 1 in the outer loop of primes(n) (since all even numbers >2 aren't primes). This cuts the number of iterations in half.
  • Stop the inner loop early: Instead of checking primeNumbers[j] <= Math.sqrt(i), once primeNumbers[j] * primeNumbers[j] > i, you can break immediately—no need to check larger primes, as they can't divide i without a smaller prime factor already being found.

• Precompute primes for repeated use:

  • If you call primeFactors multiple times, precompute primes up to your maximum needed value once (using the sieve) instead of generating them every time. This amortizes the prime generation cost across all calls, saving a ton of repeated work.

• Direct trial division for factorization (skip prime generation upfront):

  • Instead of generating all primes up to sqrt(n) first, do trial division directly on n with odd numbers starting from 3, checking divisibility up to sqrt(x) (updating sqrt(x) as x shrinks). This avoids generating all primes upfront, which can save time if n has small factors (you might exit early without checking all primes up to sqrt(n)). The worst-case time here is O(sqrt(n)/ln(n)), which is better than the original approach's O(n^(3/4)/ln(n)).

内容的提问来源于stack exchange，提问作者Vishu Bhardwaj