Abstract / Summary

Find how many different prime numbers multiply into the product of all numbers in the array

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Math
• Number Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method distinctPrimeFactors that receives a list of integers and returns the count of unique prime factors appearing across all numbers in the list. The algorithm builds a mapping from each integer in the range [2, max(nums)] to the set of its prime divisors, then merges the factor sets for the specific input values and finally reports the size of the combined set.

Core Data Structures

The method creates a defaultdict whose values are sets. This container, named factors, automatically initializes an empty set for any new key, allowing prime factors to be accumulated without explicit existence checks. A second ordinary set, called all, is used to collect the union of factor sets for the numbers supplied in nums.

factors = defaultdict(set)
...
all = set()

Prime Factor Extraction Loop

The heart of the algorithm iterates over every integer i from 2 up to the maximum value present in nums. For each i a temporary variable current holds a mutable copy that is reduced as prime divisors are discovered.

for i in range(2, max(nums)+1):
    current = i
    # even numbers
    while (current & 1) == 0:
        factors[i].add(2)
        current >>= 1

    # odd numbers
    for j in range(3, i+1, 2):
        while current > 1 and current % j == 0:
            factors[i].add(j)
            current //= j

The inner logic is split into two phases. The first phase repeatedly extracts the factor 2 by testing the least-significant bit with a bitwise AND and then shifting right, which is equivalent to dividing by two but avoids the division operator. Each successful extraction records 2 in the factor set for i.

The second phase examines odd candidates j starting at 3 and stepping by 2. For each candidate, a nested loop divides current by j as long as j evenly divides it, adding j to the factor set each time. The loop bound i+1 guarantees that every possible divisor up to i is considered, ensuring complete factorization.

Aggregating Distinct Factors

After the factor map is populated, the method iterates over the original input list. For each number n it merges the precomputed factor set factors[n] into the cumulative set all using the in-place union operator |=.

for n in nums:
    all |= factors[n]

When the loop finishes, all contains every prime factor that appears in any of the input numbers. The final result is obtained by measuring the cardinality of this set.

return len(all)

Edge Cases Handled

The algorithm explicitly treats even numbers through a dedicated bitwise loop, which correctly handles values that are powers of two, such as 2, 4, 8, and so on. By continuously shifting right until the number becomes odd, it captures the factor 2 exactly once per distinct prime, regardless of multiplicity.

For odd numbers, the nested divisor loop processes each odd candidate j. Because the inner loop continues dividing current while the divisor remains applicable, numbers that contain repeated odd prime factors (for example, 9 = 3 × 3) are still reduced to 1, and the prime factor 3 is recorded only once in the set, preserving uniqueness.

The use of a range that starts at 2 ensures that the method never attempts to factorize 0 or 1, which have no prime factors. If the input list contains such values, they simply contribute an empty set to the union operation, leaving the distinct count unaffected.

Performance Optimizations

A notable optimization is the use of a bitwise test (current & 1) == 0 to detect evenness, which is faster than a modulo operation. Coupled with the right-shift assignment current >>= 1, the code eliminates repeated division by two, reducing the overhead for numbers with many trailing zeros in binary representation.

Storing factor sets in a defaultdict(set) avoids repeated existence checks or conditional initializations, allowing direct insertion with add. This design choice streamlines the accumulation of prime factors and leverages the constant-time characteristics of set insertion.

The union of factor sets is performed incrementally with the |= operator, which updates the cumulative set in place. This avoids the creation of intermediate temporary sets for each iteration, thereby conserving memory and reducing allocation costs.

By precomputing factor sets for the entire range up to the maximum input value, the method eliminates redundant factorization work when the same number appears multiple times in nums. Each integer is factored exactly once, and subsequent lookups retrieve the already computed set, providing a clear reuse advantage.

Imagine having a big box of colorful building blocks where each number is represented by a special combination of smaller pieces called prime factors. The code starts by making a giant list of all the tiny building blocks needed to create every number in your set. First, it looks at the numbers and checks to see if two can fit inside them. If the number is even, it keeps taking out twos until it cannot anymore. Then, it tries to see what other little odd numbers fit inside that original number by trying them one by one. Once it finds all the tiny pieces that make up a specific number, it puts them in a special bag for that number. After doing this for every number in the list, it collects all these prime building blocks into one big pile. Because it uses a special kind of bag that does not allow duplicates, even if many numbers share the same tiny factor, it only keeps one of each. Finally, it just counts how many different types of building blocks are in that big pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality