---

Clojure Prime Factors: A Complete Guide from Zero to Hero

Calculating the prime factors of a number in Clojure is a classic problem that beautifully showcases the language's functional elegance. It involves iteratively dividing a number by its prime divisors, starting from 2, and collecting these factors until the number is reduced to 1, revealing its fundamental components in a clean, recursive manner.

Ever stared at a number, like 147 or 864, and felt that familiar programmer's itch? The deep-seated curiosity to dismantle it, to see what it's truly made of? This process, known as prime factorization, is not just a mathematical curiosity; it's a foundational concept in computer science, cryptography, and algorithm design. Many developers, however, hit a wall when trying to implement this in a functional paradigm. Imperative loops and mutable state seem so much easier, but they miss the beauty and safety of languages like Clojure.

This guide is your solution. We will demystify prime factorization and translate its logic into elegant, idiomatic Clojure code. You will not only solve the problem but also gain a deeper appreciation for functional concepts like recursion, immutability, and lazy evaluation. By the end, you'll be able to write a robust prime factorization function from scratch and understand the principles that make it work.

---

What Are Prime Factors and Why Do They Matter?

Before we dive into the Clojure implementation, it's crucial to solidify our understanding of the core concepts. The "what" and "why" are just as important as the "how," especially when building robust and meaningful software.

Defining the Building Blocks: Prime Numbers and Factorization

At its heart, this problem revolves around two simple ideas: prime numbers and factors.

• Factor: A factor of a number is any integer that divides it without leaving a remainder. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12.
• Prime Number: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and so on. Note that 2 is the only even prime number.

Prime Factorization is the process of finding which prime numbers multiply together to make the original number. This leads us to a cornerstone of mathematics: The Fundamental Theorem of Arithmetic. This theorem states that every integer greater than 1 is either a prime number itself or can be represented as a product of prime numbers, and this representation is unique, apart from the order of the factors.

For example, let's break down the number 60:

• 60 = 2 × 30
• 30 = 2 × 15
• 15 = 3 × 5

Putting it all together, the prime factorization of 60 is 2 × 2 × 3 × 5. No other combination of prime numbers will produce 60. This uniqueness is what makes prime factorization so powerful.

Why Programmers Must Care About Prime Factors

This isn't just an abstract math problem from the kodikra learning path. Prime factorization is a critical component in several areas of computer science and technology:

• Cryptography: This is the most famous application. Public-key cryptography systems like RSA rely on the fact that it is computationally easy to multiply two very large prime numbers together, but extremely difficult to do the reverse—to find the prime factors of the resulting product. The security of your online transactions often depends on this difficulty.
• Algorithm Design: Many algorithms in number theory, such as Pollard's rho algorithm for integer factorization or algorithms for finding the Greatest Common Divisor (GCD), are based on prime factors.
• Data Structures: Hash functions, which are essential for data structures like HashMap or HashSet, sometimes use prime numbers to help distribute keys more evenly and reduce collisions.
• Technical Interviews: Problems involving prime numbers and factorization are classic interview questions used to test a candidate's understanding of algorithms, recursion, and computational complexity.

Mastering this concept in a functional language like Clojure not only solves the immediate problem but also equips you with patterns that are applicable across a wide range of programming challenges.

---

How to Compute Prime Factors: The Clojure Way

Now we get to the core of the article: translating the logic of prime factorization into idiomatic Clojure code. We'll use a common and intuitive algorithm called Trial Division.

The Trial Division Algorithm Explained

The trial division method is straightforward. Given a number n, we try to divide it by a sequence of potential divisors, starting with the smallest prime, which is 2.

1. Start with a divisor of 2.
2. While the number n is divisible by the current divisor, keep dividing n by it and add the divisor to our list of prime factors.
3. Once n is no longer divisible by the current divisor, increment the divisor to the next number (3, then 4, then 5, and so on).
4. Repeat this process until the number n becomes 1.

Let's trace this with our example, n = 60:

• Start with divisor = 2. Is 60 divisible by 2? Yes. New n is 30. Factors: [2].
• Is 30 divisible by 2? Yes. New n is 15. Factors: [2, 2].
• Is 15 divisible by 2? No. Increment divisor to 3.
• Is 15 divisible by 3? Yes. New n is 5. Factors: [2, 2, 3].
• Is 5 divisible by 3? No. Increment divisor to 4.
• Is 5 divisible by 4? No. Increment divisor to 5.
• Is 5 divisible by 5? Yes. New n is 1. Factors: [2, 2, 3, 5].
• Now n is 1, so the algorithm terminates. The result is [2, 2, 3, 5].

This process is inherently recursive, which makes it a perfect fit for a functional language that avoids mutable state and traditional for loops.

ASCII Art Diagram: The Algorithm's Flow

Here is a visual representation of the trial division logic we just discussed. This flow is what we will translate into Clojure code.

    ● Start (Input: n)
    │
    ▼
  ┌───────────────────┐
  │ Initialize:        │
  │ divisor = 2        │
  │ factors = []       │
  └─────────┬─────────┘
            │
            ▼
  ◆ Is n > 1 ? ───────── No ───▶ ● Return factors & End
  │
 Yes
  │
  ▼
  ◆ Is n divisible by divisor?
 ╱                            ╲
Yes                          No
 │                            │
 ▼                            ▼
┌──────────────────┐      ┌──────────────────┐
│ Add divisor to factors │      │ Increment divisor   │
│ n = n / divisor    │      │ (divisor = divisor + 1) │
└──────────────────┘      └──────────────────┘
 │                            │
 └───────────┬──────────────┘
             │
             ▼
        (Loop back to "Is n > 1?")

The Clojure Implementation

In Clojure, the most idiomatic and efficient way to implement this kind of recursive algorithm is with the loop/recur special form. This provides the power of recursion without the risk of a stack overflow error, as it's compiled down to a simple JVM jump instruction (a loop).

Here is the complete, well-commented solution from the kodikra.com curriculum.

(ns kodikra.prime-factors
  (:gen-class))

(defn of
  "Calculates the prime factors of a natural number `n` using trial division."
  [n]
  ;; Use loop/recur for efficient, stack-safe recursion.
  (loop [current-num n          ; The number we are currently trying to factor.
         divisor 2            ; The potential prime factor we are testing.
         prime-factors []]    ; An accumulator for our results (a vector).

    ;; Base Case: If the number is less than or equal to 1, we have factored everything.
    ;; The process is complete, so we return the accumulated prime factors.
    (if (<= current-num 1)
      prime-factors

      ;; Recursive Step:
      (if (zero? (rem current-num divisor))
        ;; Condition 1: The current divisor cleanly divides the number...
        (recur (/ current-num divisor)      ; ...so, we divide the number by the divisor.
               divisor                      ; ...and check the SAME divisor again (e.g., for 12 -> 2, 2, 3).
               (conj prime-factors divisor)) ; ...and add the divisor to our list of factors.

        ;; Condition 2: The divisor does not divide the number cleanly...
        (recur current-num                  ; ...so, we keep the number as is.
               (inc divisor)                ; ...and try the next potential divisor.
               prime-factors)))))          ; ...the list of factors remains unchanged for this step.

Running the Code

You can run this function in a Clojure REPL (Read-Eval-Print Loop). After defining the function, you can test it with various inputs.

# Start a Clojure REPL
$ clj

# Load the namespace (assuming the file is in src/kodikra/prime_factors.clj)
user=> (require '[kodikra.prime-factors :as pf])

# Test with a simple case
user=> (pf/of 2)
[2]

# Test with the example from the instructions
user=> (pf/of 60)
[2 2 3 5]

# Test with a larger number
user=> (pf/of 901255)
[5 17 23 461]

# Test with a prime number
user=> (pf/of 97)
[97]

Detailed Code Walkthrough

Let's break down the function piece by piece to understand exactly what's happening.

1. (defn of [n] ...)

   This defines a function named of that accepts one argument, n, which is the number we want to factorize.

2. (loop [current-num n divisor 2 prime-factors []])

   This is the heart of our function. loop establishes a recursion point with three local bindings:

   • current-num: Initialized with the input n. This is the value that will be progressively divided down.
   • divisor: Initialized to 2, our first potential prime factor.
   • prime-factors: An empty vector [] that will accumulate our results. Using a vector is efficient for appending elements with conj.
3. (if (<= current-num 1) prime-factors ...)

   This is our base case. The recursion must have a stopping point. Once current-num has been divided all the way down to 1 (or less, for safety), the factorization is complete. At this point, we simply return the prime-factors vector we've been building.

4. (if (zero? (rem current-num divisor)) ... ...)

   This is the main logical check. (rem current-num divisor) calculates the remainder of the division. (zero? ...) checks if that remainder is zero. In short, it asks: "Does divisor divide current-num evenly?"

5. The "Divisible" Branch: (recur (/ current-num divisor) divisor (conj prime-factors divisor))

   If the number is divisible, we call recur to jump back to the start of the loop with updated values:

   • (/ current-num divisor): The number is updated to its new, smaller value.
   • divisor: The divisor is not changed. This is a crucial detail! If a number is 12, we need to check for the factor 2 twice (2, 2, 3). By keeping the divisor the same, we handle repeated factors correctly.
   • (conj prime-factors divisor): We add the successful divisor to our accumulator. conj (conjoin) is Clojure's idiomatic way to add an element to a collection.
6. The "Not Divisible" Branch: (recur current-num (inc divisor) prime-factors)

   If the number is not divisible by the current divisor, we call recur with a different set of updates:

   • current-num: The number remains unchanged.
   • (inc divisor): We increment the divisor to try the next integer (2 becomes 3, 3 becomes 4, etc.).
   • prime-factors: The list of factors also remains unchanged in this step.

This cycle continues, either reducing the number or incrementing the divisor, until the base case is met. The result is a purely functional, highly readable, and efficient solution.

---

When to Consider Alternative Approaches

The trial division algorithm we've implemented is fantastic for its simplicity and for handling numbers of a reasonable size (up to millions or billions). However, like any algorithm, it has its limitations. For a senior developer, knowing when not to use a particular tool is as important as knowing how to use it.

Limitations of Trial Division

The primary weakness of our algorithm is its performance with very large numbers, especially those that are the product of two large primes (the kind used in cryptography).

• Time Complexity: The worst-case time complexity is approximately O(sqrt(n)). This is because we might have to check for divisors all the way up to the square root of the input number n. While this is much better than O(n), it becomes prohibitively slow for numbers with, say, 100 digits.
• Unnecessary Checks: Our simple implementation checks every integer after 2 (3, 4, 5, 6, 7, 8...). This is inefficient because we don't need to check composite numbers like 4, 6, or 8. If a number is divisible by 4, it would have already been fully divided by 2.

Potential Optimizations and Advanced Algorithms

For educational purposes and most practical applications, our solution is excellent. But if you were tasked with factoring massive numbers, you would explore more advanced methods.

Simple Optimizations to Trial Division:

1. Handle 2 Separately: First, divide out all factors of 2. After that, the remaining number must be odd.
2. Check Only Odd Divisors: Once all factors of 2 are gone, you only need to check odd divisors (3, 5, 7, 9, 11...). This immediately cuts the number of checks in half. The `9` check is redundant but the pattern is `i = i + 2`.
3. Stop at sqrt(n): You only need to test divisors up to the square root of the current number. If you haven't found a factor by then, the remaining number itself must be prime.

Advanced Factoring Algorithms:

For numbers well beyond the reach of trial division, mathematicians and computer scientists use more sophisticated algorithms:

• Pollard's Rho Algorithm: A probabilistic algorithm that is much faster for numbers with small prime factors.
• Quadratic Sieve (QS): One of the fastest algorithms for factoring numbers up to about 100 digits.
• General Number Field Sieve (GNFS): The most efficient classical algorithm known for factoring integers larger than 100 digits. This is the algorithm used to break RSA challenges.

Pros & Cons: Trial Division vs. Advanced Methods

Aspect	Trial Division (Our Clojure Solution)	Advanced Algorithms (e.g., GNFS)
Implementation Complexity	Low. Easy to understand and write in a few lines of code.	Extremely High. Requires deep knowledge of number theory and advanced mathematics.
Performance	Excellent for small to medium numbers (up to ~10^12). Becomes very slow for large numbers.	Massively faster for large numbers. The only feasible option for cryptographic-scale integers.
Use Case	General programming tasks, competitive programming, technical interviews, educational purposes.	Cryptanalysis, academic research, breaking security challenges.
Code Readability	High. The logic directly follows the definition of factorization.	Low. The code is often opaque without the corresponding mathematical background.

ASCII Art Diagram: Conceptual Performance Scaling

This diagram illustrates where trial division shines and where it falls short, necessitating more complex solutions.

     Input Number Size (n)
              │
              ▼
    small n  ├─╼ Trial Division: FAST & SIMPLE ✅
   (e.g., 60) │
              │
   medium n  ├─╼ Trial Division: Still Good, Gets Slower... ⏳
(e.g., 10^9)  │
              ▼
    large n   ├─╼ Trial Division: BECOMES IMPRACTICAL 🐢
(e.g., 10^18) │
              │
              │
              └─╼ Advanced Algorithms (Pollard's Rho, etc.): REQUIRED 🚀
              │
              ▼
   very large n
 (Cryptography)

Understanding these trade-offs is a key part of moving from a junior to a senior engineering mindset. Always choose the right tool for the job. For the vast majority of development tasks, a clean trial division implementation is more than sufficient. Explore our full Clojure language guide for more on performance and idiomatic patterns.

---

Frequently Asked Questions (FAQ)

1. What is the prime factorization of 1?

By convention, 1 is the multiplicative identity and is considered neither prime nor composite. Its prime factorization is an empty set of factors. Our function correctly handles this by returning an empty vector: (of 1) evaluates to [].

2. Why do we start the divisor at 2?

We start at 2 because it is the smallest prime number. Since every composite (non-prime) number is a product of primes, the smallest possible prime factor any even number can have is 2, and the smallest any odd composite can have is 3. Starting at 2 ensures we cover all possibilities from the ground up.

3. Is this Clojure solution tail-recursive?

Yes, absolutely. By using the loop/recur special form, we ensure tail-call optimization (TCO). The call to recur is the very last action in each branch of the logic (it's in the "tail position"). This means the Clojure compiler transforms the recursion into a simple loop, preventing the call stack from growing and thus avoiding a StackOverflowError, even for numbers that require many iterations.

4. How does this function handle very large numbers (BigInt)?

Clojure, running on the JVM, has excellent support for arbitrary-precision integers. If you pass a number that exceeds the capacity of a standard 64-bit long, Clojure automatically promotes it to a clojure.lang.BigInt. All standard arithmetic operations (/, rem, inc) work seamlessly with these large numbers. Therefore, our function will work correctly with very large numbers, though it may be slow due to the algorithm's complexity.

5. Could I use lazy sequences to solve this problem?

Yes, a solution using lazy sequences is a very elegant and idiomatic alternative in Clojure. It separates the generation of potential factors from the process of testing them. While slightly more advanced, it can be more composable. Here is a conceptual sketch:

(defn lazy-factors [n]
  (letfn [(factors-of [num divisor]
            (when (> num 1)
              (if (zero? (rem num divisor))
                (lazy-seq (cons divisor (factors-of (/ num divisor) divisor)))
                (lazy-seq (factors-of num (inc divisor))))))]
    (factors-of n 2)))

;; Usage: (lazy-factors 60) -> (2 2 3 5)
    

This approach produces a lazy sequence of factors, which are only computed as they are needed. It's a powerful demonstration of Clojure's functional capabilities.

6. What is the time complexity of this algorithm?

The time complexity is roughly proportional to the largest prime factor of the number, or O(sqrt(n)) in the worst case (when n is a prime number or a product of two large primes). For a number n, the loop for the divisor will run at most up to sqrt(n), because if n has a factor larger than its square root, it must also have a corresponding factor smaller than it, which would have been found already.

7. Are there built-in Clojure libraries for prime factorization?

Clojure's core library does not include a prime factorization function, as it's considered more of an algorithmic task than a utility function. However, the ecosystem has several third-party math and number theory libraries, like clojure.math.numeric-tower, which provide functions for primality testing, factorization, and other related tasks if you don't want to implement them yourself for a production application.

---

Conclusion: From Theory to Functional Mastery

We've journeyed from the fundamental theory of prime numbers to a practical, elegant, and efficient implementation in Clojure. By leveraging the loop/recur construct, we created a solution that is not only correct but also embodies the functional principles of immutability and recursion over iteration. This approach yields code that is readable, safe from stack overflows, and easy to reason about.

Furthermore, we explored the boundaries of our algorithm, understanding its performance characteristics and acknowledging when more advanced techniques would be necessary. This critical thinking is what separates rote coding from true software engineering. The prime factors problem, as featured in the kodikra.com Module 4 path, serves as a perfect vehicle for internalizing these core functional programming patterns.

You now have a solid understanding of how to approach mathematical algorithms in a functional style. The next step is to apply these patterns to new challenges and continue exploring the power and beauty of the Clojure language. Dive deeper into our comprehensive Clojure learning resources to continue your journey from apprentice to master.

Disclaimer: All code snippets and examples are based on Clojure 1.11+ and Java 11+. While the core logic is timeless, specific library functions and performance characteristics may evolve in future versions.

---

Published by Kodikra — Your trusted Clojure learning resource.