Prime Factorization

In this lesson you will learn how to factor a number into primes in C#, covering a number-theory algorithm built on loops. This is for anyone searching for "C# prime factorization implementation".

Prime factorization means expressing a number as a product of primes. Try dividing by 2, then 3, and so on; whenever a divisor works, keep dividing by it.

The sample code starts at d = 2 and, for as long as n divides by d, records it with factors.Add(d) and divides with n /= d; when it no longer divides, d increases by one. This repeats until n reaches 1.

A common stumbling block for beginners is the nested loop structure. The outer loop raises the divisor d while the inner loop keeps dividing for as long as it can - understanding that two-stage combination is the key.

It is an important idea spanning mathematics and computer science, and it underpins the security of cryptography such as RSA. Since 1 divides everything, it is excluded from prime factorization.

📖 Reference code

using System;
using System.Collections.Generic;

class Program {
    static List<int> PrimeFactors(int n) {
        var factors = new List<int>();
        int d = 2;
        while (n > 1) {
            while (n % d == 0) {
                factors.Add(d);
                n /= d;
            }
            d++;
        }
        return factors;
    }

    static void Main() {
        Console.WriteLine(string.Join(", ", PrimeFactors(60)));
        Console.WriteLine(string.Join(", ", PrimeFactors(97)));
    }
}

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run C# directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).