Leetcode #2521: Distinct Prime Factors of Product of Array

Jan 04 2026

Table of contents

• Problem statement
• A first attempt
• A different approach: the sieve of Eratosthenes
  • Optimization: skipping a few iterations
  • Closing thoughts

A fun Leetcode problem I solved recently was #2521. In this blog post I'll discuss a couple of solutions to it.

Problem statement🔗

The problem statement simply asks us to find the number of distinct prime factors in the product of the elements of an array of positive integers. So for example the product of the elements of the array [1, 2, 6, 7] is 84, whose prime factors are [2, 2, 3, 7], which has 3 distinct elements, so our answer should be 3.

The array can have at most $10,000$ elements and each element lies between $2$ and $1000$, both inclusive.

A first attempt🔗

A useful observation here is that we don't even need to multiply together all the array elements. We're only trying to count the distinct prime factors of the product, so if we build up a set of prime factors for each element and union all of them together and find its size, we'd be done. This way we sidestep issues with loss of precision or numeric type overflows.

We could of course get around the latter restriction by using a language like Python or a language library that supports arbitrary-precision integers, but that seems like overkill when we already have the simpler idea discussed above.

How do we find the prime factors of each element of the array? My first thought was to build up a list of primes from 2 to 1000, since that's the range the array elements lie in. Then we could check each number against the list of primes, like so:

 1class Solution:
 2    def distinctPrimeFactors(self, nums: List[int]) -> int:
 3        def is_prime(n):
 4            return not any(n % i == 0 for i in range(2, n))
 5        PRIMES = [k for k in range(2, 1001) if is_prime(k)]
 6        seen = set()
 7        for num in nums:
 8            for prime in PRIMES:
 9                if prime > num:
10                    break
11                if prime not in seen:
12                    if num % prime == 0:
13                        seen.add(prime)
14        return len(seen)

In this code:

• To construct the list of primes we use a naive algorithm that simply marks a number k as prime if it has no integer factors in the set $\{2, 3, 4, ..., k-1\}$. There are faster, more sophisticated algorithms to check primality, but this is just a first attempt.

• The if prime > num: break clause on lines 11 and 12 lets us skip pointless checks for num % prime == 0, which can never be true if prime is greater than num.

This solution passes all testcases, but the runtime looks to be suboptimal.

Let's analyze the runtime. I'm going to assume that the % (modulo) operation is constant time to simplify calculations.

1. Let's use $N$ to denote the upper bound of each positive integer in the array. In our problem statement, this is $1000$. Let's also use $M$ to denote the number of elements in our array.

2. We perform $\Theta(N^2)$ operations to compute the list of all primes up to $N$, because for each number $2 \le n \le N$ we check if it's prime by iterating from $2 \le i \le n$.

3. Then, for each number in the array we perform at most $P$ checks, where $P$ is the number of primes between $1$ and $1000$.

Our total runtime is then $\Theta(N^2) + O(MP)$. Note that $P$ grows slower than $N$. For $N = 1000$, $P$ is just $168$.

This $\Theta(N^2)$ term is not great. Can we get a faster runtime?

One thing we can do is: when checking if an integer $n$ is prime, we can save some time by running $k$ from $2$ to $\sqrt(n)$ instead of $n-1$.

 1class Solution:
 2    def distinctPrimeFactors(self, nums: List[int]) -> int:
 3        def is_prime(n):
 4            upper_bound = 1 + math.ceil(math.sqrt(n)) if n > 2 else n
 5            return not any(n % i == 0 for i in range(2, upper_bound))
 6        PRIMES = [k for k in range(2, 1001) if is_prime(k)]
 7        seen = set()
 8        for num in nums:
 9            for prime in PRIMES:
10                if prime > num:
11                    break
12                if prime not in seen:
13                    if num % prime == 0:
14                        seen.add(prime)
15        return len(seen)

We now iterate up to the ceiling of the square root of $n$. The edge case to consider is $n=2$. If we did that for $n=2$ we'd end up with an empty range, so instead we iterate up to $n$ in that case.

Running this, we get:

A different approach: the sieve of Eratosthenes🔗

There isn't much else to refine in the above approach. We'll need to try something else.

A faster way to generate prime numbers is the sieve of Eratosthenes. This is an algorithm to generate all prime numbers up to a given number, in this case $1000$. The simplest implementation of this algorithm looks like this in pseudocode.

Translating this to Python, we'd have something like

1isPrime = [True for _ in range(N+1)]
2for i in range(2, N):
3    if isPrime[i]:
4        for j in range(2*i, N+1, i):
5            isPrime[j] = False

It turns out we can extend the sieve in a clever way — we can store the smallest prime factor for each number instead of a simple boolean value. I read about this approach in this GeeksForGeeks post.

1N = 1000  # Upper bound on primes to generate, as per the problem statement
2smallestPrimeFactor = [i for i in range(N+1)]
3for i in range(2, N):
4    if smallestPrimeFactor[i] == i:  # prime!
5        for j in range(2*i, N+1, i):
6            if smallestPrimeFactor[j] == j:
7                smallestPrimeFactor[j] = i

Compare this code to the previous code and notice the extra if condition on line 6. Why do we need it? smallestPrimeFactor[j] != j means that in a previous iteration, for a smaller value of i, we had updated smallestPrimeFactor[j]. And if that was the case, then we don't want to overwrite that value with this current, larger value of i.

Fair enough. But why store the smallest prime factor for each number at all? Because it gives us a quick way to factorize any number lying between $1$ and $N$:

 1# Returns the prime factorization of `num` in sorted ascending order.
 2def factorize(num: int, smallestPrimeFactor: list[int]) -> list[int]:
 3    prime_factors = []
 4    while num > 1:
 5        prime = smallestPrimeFactor[num]
 6        prime_factors.append(prime)
 7        num //= prime
 8    return prime_factors

It's straightforward to extend this function to instead dump all prime factors for a given number into a set external to the function. When we're done calling this function for every number in the array, we will have a set consisting of all of the distinct prime factors of the product of the entire array!

1distinctPrimes = set()
2def factorizeAndUpdateDistinctSet(num: int, smallestPrimeFactor: list[int], distinctPrimes: set[int]):
3    while num > 1:
4        prime = smallestPrimeFactor[num]
5        distinctPrimes.add(prime)
6        num //= prime

And putting it all together, we have a working solution:

 1N = 1000
 2smallestPrimeFactor = [i for i in range(N+1)]
 3for i in range(2, N+1):
 4    if smallestPrimeFactor[i] == i:  # prime!
 5        for j in range(2*i, N+1, i):
 6            if smallestPrimeFactor[j] == j:
 7                smallestPrimeFactor[j] = i
 8
 9distinctPrimes = set()
10def factorizeAndUpdateDistinctSet(num, smallestPrimeFactor, distinctPrimes):
11    while num > 1:
12        prime = smallestPrimeFactor[num]
13        distinctPrimes.add(prime)
14        num //= prime
15
16for num in nums:
17    factorizeAndUpdateDistinctSet(num, smallestPrimeFactor, distinctPrimes)
18return len(distinctPrimes)

...and it's much faster than before!

Let's analyze the runtime for this algorithm. Again, I'm going to assume that integer division (//) is constant time to simplify calculations. Again, not true, but interestingly, integer division is about as fast as the modulo operation is, so we're making the "same" deliberate error when comparing these two algorithms.

1. In the phase where we compute the smallest prime factor for each number, we update each element of the smallestPrimeFactor array at most once. So that's $\Theta(N)$, because that's how many elements the array has.

2. Next, we factorize each member of the array, spending $O(Q)$ time on each, where $Q$ is the maximum number of not-necessarily-distinct prime factors that any element of the array has. It would be nice if we could get a not-too-coarse upper bound on $Q$, to keep things simple. As it happens, we can! To get as a high value as possible for the number of not-necessarily-distinct prime factors of a number, we can just keep multiplying by the smallest prime number there is, $2$. Notice how $512 = 2^9$ has 9 not-necessarily-distinct prime factors, and so we can confidently say that no number under $1000$ has more than 10 not-necessarily-distinct prime factors.

3. In general, a nice not-too-coarse upper bound for $Q$ would be $\log_{2}(N)$ And so our running time for the factorization phase is $\Theta(N\log_{2}(N))$.

So our total runtime for this algorithm is $\Theta(N) + \Theta(N\log_2{N})$, which is just $\Theta(N\log_2{N})$. Much better than our earlier runtime!

Our space complexity is $\Theta(N) + O(MQ)$:

• The first term $\Theta(N)$ comes from the smallestPrimeFactor array.
• The second term $O(MQ)$ from the factorization step, because each of the $M$ array elements has at most $Q$ not-necessarily-distinct prime factors. Note that at each step we check membership and then insert into the Python set, and the average case complexity (not worst case!) of both operations doing so is constant-time. For more details, please see the Python wiki.

Optimization: skipping a few iterations🔗

Every time we encounter a prime number, we "cross out" (set the corresponding index in smallestPrimeFactor) all of its multiples. To do so we'd move the index $j$ from $2i$ all the way up to $N+1$ (upper bound exclusive) by steps of $i$, where $N$ is the upper bound on primes that we want to generate.

But there's a nice optimization available to us. Consider a prime number $i$. By the time our iteration variable $j$ reaches $i$, we have already processed every multiple of every prime that was smaller than $i$. For example:

• we had already processed every multiple of $2$, including $2i$
• we had already processed every multiple of $3$, including $3i$
• ...and so on

To be precise, by the time $j$ reaches $i$, we have already processed every multiple of $i$ smaller than $i \times i$. We know for a fact that we haven't already processed $i \times i$ itself, because $i$ is prime and therefore would not be part of any of the previous iterations.

And so we can start our iteration from $i^2$ instead of $2i$, skipping a few if checks that would always have failed (because smallestPrimeFactor[i] would've been set to something other than i by that point).

1N = 1000  # as per the problem statement
2smallestPrimeFactor = [i for i in range(N+1)]
3for i in range(2, N):
4    if smallestPrimeFactor[i] == i:  # prime!
5        for j in range(i*i, N+1, i):
6            if smallestPrimeFactor[j] == j:
7                smallestPrimeFactor[j] = i

Closing thoughts🔗

• Notice how we use linear space in the sieve method: we allocate memory upfront for every number from $0$ to $N$ to store each number's smallest prime factor. This works well enough when our input is quite bounded as in the problem statement, with a maximum value of only $1000$.

• In both the naive approach and the sieve approach, we perform some precomputation. In the first method, we precomputed all primes up to $1000$. In the second method, we precomputed the smallest prime factor for every number up to $1000$. Logic like this should ideally live in the constructor (def __init__(self):) so that we do it only once and then reuse the solver object to answer queries for several inputs.

Thanks for reading!

[1] It isn't constant time, but as it turns out, if implemented correctly, it's as fast as other operations like multiplication and computing modular remainders. This allows us to simplify our runtime analysis.