What is Prime Factorization in C- Embedded C Programming Course

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Prime Factorization in C

Free C tutorial: write a prime factorization program in C with functions, trial division and clean embedded-friendly code.

Prime factorization in C is one of the best exercises for learning how functions, loops and integer arithmetic work together. In this lecture of our free C programming course you will break a number such as 56 into 2, 2, 2 and 7 using a short, well-structured function, and you will learn why the same idea shows up in real embedded C programming work such as timer and clock configuration. If you are looking for a free embedded C course that explains the reasoning behind every line, you are in the right place.

What You Will Learn

  • What a prime factor is and why every integer above 1 has exactly one prime factorization
  • How trial division works and how to turn it into a clean C function
  • Why the search can stop at the square root of the remaining value
  • How to return factors to the caller through an array instead of printing them
  • How to avoid integer overflow, infinite loops and off-by-one mistakes
  • Where prime factorization is used in C programming for embedded systems

Prerequisites

  • Function definition, prototype and return statement (earlier lectures of this chapter)
  • The for and while loops and the remainder operator %
  • Fixed-width integer types from stdint.h
  • A working GCC installation on Linux, or any C99 compiler

What Is Prime Factorization?

A prime number is an integer greater than 1 whose only divisors are 1 and itself. The numbers 2, 3, 5, 7, 11 and 97 are prime. A composite number can be written as a product of primes, and the fundamental theorem of arithmetic says that this product is unique apart from the order of the factors. That uniqueness is what makes the problem well defined: there is one correct answer for every input, so a program can be tested against known results.

NumberPrime factorizationComment
562 x 2 x 2 x 7Repeated factor 2
982 x 7 x 7Repeated factor 7
12111 x 11Perfect square of a prime
9797Prime, factorization is the number itself
3602 x 2 x 2 x 3 x 3 x 5Several different primes
1noneNeither prime nor composite

Key idea

If you always divide out the smallest possible divisor first, every divisor you accept is automatically prime. A composite divisor such as 4 can never divide the value, because the factors 2 and 2 have already been removed.

How Trial Division Finds Prime Factors in C

Trial division is the simplest factorization method. Start with a candidate divisor of 2. While the candidate divides the value evenly, report it and shrink the value. When it no longer divides, move to the next candidate. Repeat until the candidates are too large to matter. The method needs only a loop, a remainder test and a division, which is why it fits comfortably into a first function-based program.

Step by step on the number 360

Trial division trace for 360
value 360divisor 2360 % 2 = 0 : emit 2
value 180divisor 2180 % 2 = 0 : emit 2
value 90divisor 290 % 2 = 0 : emit 2
value 45divisor 245 % 2 = 1 : move on
value 45divisor 345 % 3 = 0 : emit 3
value 15divisor 315 % 3 = 0 : emit 3
value 5divisor 44 is larger than 5 / 4 : stop looping
leftover 5 is primeemit 5

Notice that the value shrinks while the loop runs. The stopping test is compared against the shrinking value, not the original input. That single detail is what makes the algorithm fast for numbers with many small factors.

Why the loop can stop at the square root

Suppose the remaining value is composite. Then it has at least one divisor that is no larger than its square root, because two divisors both bigger than the root would multiply to something larger than the value itself. So once the candidate divisor squared exceeds the remaining value, nothing left can divide it, and whatever remains (if it is greater than 1) must be prime. In C we write the test as divisor <= value / divisor instead of divisor * divisor <= value. The division form can never overflow, while the multiplication form wraps around for large 32-bit values and can create an endless loop.

Decision flow inside the factor loop
start: divisor = 2→divisor <= value / divisor ?
no →value > 1 : print leftover prime→done
yes →value % divisor == 0 ?
yes →print divisor, value = value / divisor→ test again
no →divisor = divisor + 1→ first test

Iterative Prime Factorization Program in C

The program below has two functions. ep_print_prime_factors() prints the factors directly, which is the easiest way to see the algorithm work. ep_factorize() stores the factors in an array supplied by the caller and returns how many there are, which is how real firmware code is normally written. Both are tested with GCC and use only C99 features.

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

/* Print prime factors of value, smallest first */
static void ep_print_prime_factors(uint32_t value)
{
    if (value < 2U) {
        printf("%u has no prime factors\n", value);
        return;
    }

    for (uint32_t divisor = 2U; divisor <= value / divisor; divisor++) {
        while (value % divisor == 0U) {
            printf("%u ", divisor);
            value /= divisor;
        }
    }

    if (value > 1U) {
        printf("%u", value);   /* leftover prime */
    }
    printf("\n");
}

/* Store factors in a caller supplied array, return how many were found */
static size_t ep_factorize(uint32_t value, uint32_t out[], size_t max_out)
{
    size_t count = 0;

    for (uint32_t divisor = 2U; divisor <= value / divisor; divisor++) {
        while (value % divisor == 0U) {
            if (count < max_out) {
                out[count] = divisor;
            }
            count++;
            value /= divisor;
        }
    }
    if (value > 1U) {
        if (count < max_out) {
            out[count] = value;
        }
        count++;
    }
    return count;
}

int main(void)
{
    uint32_t samples[] = { 56U, 98U, 121U, 97U, 360U, 1U, 4294967291U };
    uint32_t buf[32];

    for (size_t i = 0; i < sizeof samples / sizeof samples[0]; i++) {
        printf("%10u : ", samples[i]);
        ep_print_prime_factors(samples[i]);
    }

    size_t n = ep_factorize(360U, buf, 32);
    printf("360 has %zu factors, first = %u, last = %u\n", n, buf[0], buf[n - 1]);
    return 0;
}

Build and run

$ gcc -std=c99 -Wall -Wextra -O0 -o ep_factor_iter ep_factor_iter.c
$ ./ep_factor_iter
        56 : 2 2 2 7
        98 : 2 7 7
       121 : 11 11
        97 : 97
       360 : 2 2 2 3 3 5
         1 : 1 has no prime factors
4294967291 : 4294967291
360 has 6 factors, first = 2, last = 5

The last sample, 4294967291, is the largest prime that fits in a 32-bit unsigned integer. Because it is prime, the loop must test every divisor up to 65535 before it can declare the value prime. Even so, the program answers instantly on a desktop computer, which shows how much work the square root limit saves compared with testing every number up to the value itself.

Understanding the Design Choices

Why static and why uint32_t

The helper functions are marked static so they are private to the file, which is standard practice in embedded C programming because it prevents name clashes in large firmware images. The type uint32_t gives the same width on a PC and on a microcontroller. A plain int can be 16 bits on small targets, and a signed overflow is undefined behaviour in C, so unsigned fixed-width types are the safer choice for number theory code.

Why return a count instead of printing

Printing from inside a computational function ties it to a console. A microcontroller may not have one, and a test harness cannot easily inspect printed text. Returning the factors in a buffer lets the caller decide what to do: print them, compare them with expected values, or feed them into another calculation. The count returned by ep_factorize() is the true number of factors even if the buffer was too small, the same convention used by snprintf(). The caller can then detect truncation by comparing the count with the buffer size.

Design choiceBenefitCost
Print inside the functionShortest code, good for learningHard to test, needs a console
Fill a caller bufferReusable, testable, no heapCaller must size the buffer
Division-based loop boundNo overflow near the 32-bit limitOne extra division per pass
Fixed-width unsigned typesSame behaviour on every targetMust avoid negative inputs

Real-World Uses of Prime Factorization in Embedded C

  • Timer configuration: a microcontroller timer often has a 16-bit prescaler and a 16-bit auto-reload register. To get a given tick count you must split it into two factors that both fit in 16 bits. Factoring the tick count tells you which splits exist.
  • Clock trees: PLL settings are products of multipliers and dividers, so factoring a target ratio shows which register combinations can produce it exactly.
  • Scheduling: task periods that share prime factors line up often, which affects jitter and worst-case timing analysis.
  • Teaching cryptography basics: RSA relies on the difficulty of factoring large numbers. Trial division shows why small keys are weak and why real keys are hundreds of digits long.

Common Mistakes and Troubleshooting

Watch out for these bugs

  • Testing candidates against the original value. If you compare the divisor with the unchanged input, the loop runs far longer than necessary.
  • Using divisor * divisor <= value with 32-bit types. For values near the top of the range the product wraps around and the loop can run forever.
  • Forgetting the leftover prime. After the loop ends, a value above 1 is itself a prime factor. Without the final check, 98 would print only 2 and 7 and 97 would print nothing.
  • Treating 0 and 1 as ordinary inputs. Dividing by a divisor of zero or looping on zero hangs the program, so reject values below 2 first.
  • Reading a negative number into an unsigned variable. The value silently becomes a huge positive number. Validate input before calling the function.

Best Practices, Performance and Security

Best practices

  • Keep the calculation function free of input and output so it can be unit tested.
  • Name functions with a project prefix such as ep_ to avoid collisions.
  • Prefer unsigned fixed-width types for arithmetic that must never overflow silently.
  • Test with known answers: primes, perfect squares, powers of two and the largest 32-bit prime.

Performance considerations

Each loop pass costs one remainder operation. Cortex-M0 class devices have no hardware divider, so every % is a software routine taking dozens of cycles, while Cortex-M3 and M4 parts have a hardware divide instruction. A simple speedup is to test 2 once and then step the divisor by 2 over odd numbers only, which roughly halves the work. Handling 2 and 3 separately and stepping by 2 and 4 alternately removes about two thirds of the candidates.

Security considerations

Trial division is a teaching tool and a utility for small numbers. Never use it as a building block for cryptographic keys. Also remember that the running time depends on the input, so a function that factors untrusted input can be made to run for the longest possible time by feeding it a large prime. In firmware, bound the work or run it outside time-critical interrupt handlers.

Try it yourself

Modify ep_factorize() so that it also reports how many times each prime occurs, for example 360 as 2 to the power 3, 3 to the power 2 and 5 to the power 1. Then add the odd-only candidate optimization and measure the difference with the time command on the prime 4294967291.

Summary and Key Takeaways

  • Every integer above 1 has a unique prime factorization, so results can be verified exactly.
  • Dividing out the smallest divisor first guarantees that each accepted divisor is prime.
  • The loop bound divisor <= value / divisor uses the shrinking value and avoids overflow.
  • After the loop, a remaining value greater than 1 is the last prime factor.
  • A function that fills a caller buffer and returns a count is easier to test and reuse than one that prints.

Conclusion

You have built a complete prime factorization program in C and seen how three small ideas make it both correct and robust: shrink the value as you go, bound the search with a division instead of a multiplication, and keep the calculation separate from the output. The same habits apply to every function you will write for firmware. In the next lecture of this free C tutorial we solve the same problem with recursion, compare the two approaches honestly, and see why recursion needs extra care on a device with a tiny stack. Continue through the course to turn these fundamentals into solid skills in C programming for embedded systems.

Frequently Asked Questions

What is the fastest way to find prime factors in C for small numbers?

For numbers that fit in 32 bits, trial division with a square root limit is fast enough on any modern machine. Skipping even candidates after 2 makes it roughly twice as fast.

Why does the loop use value / divisor instead of the square root function?

Calling sqrt() pulls in floating point, which many microcontrollers lack in hardware, and the result can be slightly inexact. An integer division gives an exact bound with no library dependency.

Is 1 a prime number?

No. Prime numbers are defined as integers greater than 1 with exactly two divisors. The number 1 has only one divisor, so it has no prime factors and our function reports that explicitly.

Why is the largest 32-bit prime a good test case?

It forces the loop to run the maximum number of iterations and checks that the loop bound does not overflow. If the program survives that input, the arithmetic is safe for the full 32-bit range.

Can I use this code on a microcontroller without printf?

Yes. Use the ep_factorize() style function that fills a buffer. You can then send the numbers over UART or read them in a debugger without linking the heavy standard formatting code.

How do I factor numbers larger than 32 bits?

Switch the types to uint64_t and keep the same loop bound. The algorithm stays correct, but the running time grows with the square root of the value, so very large numbers need more advanced methods.

Continue Your Free Embedded C Course

Next we solve prime factorization recursively and learn how to reason about stack usage, a skill every embedded engineer needs.

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →