Prime Factorization

This lesson covers prime factorization in C, so you understand implementing a number-theory algorithm using a loop. It's for anyone searching "C prime factorization implementation."

Prime factorization expresses a number as a product of prime numbers. Try dividing starting from 2, and if it divides evenly, keep dividing by that same number — that's the procedure.

The example starts with d = 2, displaying the result while dividing n by d as long as it divides evenly; once it's no longer divisible, it increments d by 1 — repeating until n becomes 1.

A common early mistake is the nested loop structure. The key to understanding it is the combination of two levels of repetition — the outer loop increasing the divisor d, and the inner loop dividing repeatedly as long as it divides evenly.

This is an important idea spanning both math and computer science, underlying the security of cryptography (like RSA encryption) too.

📖 Reference code

#include <stdio.h>

void printPrimeFactors(int n) {
    int d = 2;
    int first = 1;
    while (n > 1) {
        while (n % d == 0) {
            if (!first) printf(" ");
            printf("%d", d);
            first = 0;
            n /= d;
        }
        d++;
    }
    printf("\n");
}

int main() {
    printPrimeFactors(60);
    printPrimeFactors(97);
    return 0;
}

✍️ 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).