Factors of a Number in C – Print All Divisors with O(√n) Loop

A C program to print factors of a number finds all positive integers that divide the number evenly (with no remainder). These are also called divisors. For 12: the factors are 1, 2, 3, 4, 6, and 12. Every number has at least two factors: 1 and itself. A number with exactly two factors is a prime number.

The efficient approach loops only up to √n instead of up to n itself. For every divisor i found below √n, its pair n/i is also a divisor — so both can be collected in a single pass.

Why Loop to √n Instead of n?

Divisors come in pairs: if i divides n, then n/i also divides n.

For n = 36: when i = 4, the pair is 36/4 = 9. Both 4 and 9 are factors.
For n = 36, i = 6: the pair is 36/6 = 6. Since i == n/i, count it once.

By checking only up to √36 ≈ 6, the loop runs 6 iterations instead of 36. For large numbers, this is a massive speedup: checking factors of 1,000,000 takes 1000 iterations instead of 999,999.

C Program to Print Factors

/* Print all factors of a number in C
 * Uses O(sqrt(n)) loop: collect small factors and their pairs,
 * then print both halves in sorted order.
 * Compile: gcc -ansi -Wall -Wextra factors.c -o factors */
#include <stdio.h>

int main(void)
{
    int num, i;
    int small[600], large[600];
    int sc = 0, lc = 0, j;

    printf("Enter a positive integer: ");
    scanf("%d", &num);

    if (num <= 0) {
        printf("Please enter a positive integer.\n");
        return 1;
    }

    for (i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            small[sc++] = i;
            if (i != num / i)
                large[lc++] = num / i;
        }
    }

    printf("Factors of %d:", num);
    for (j = 0; j < sc; j++)
        printf(" %d", small[j]);
    for (j = lc - 1; j >= 0; j--)
        printf(" %d", large[j]);
    printf("\n");
    printf("Total: %d factor(s)\n", sc + lc);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra factors.c -o factors
./factors

Sample Input and Output

Enter a positive integer: 12
Factors of 12: 1 2 3 4 6 12
Total: 6 factor(s)

Enter a positive integer: 28
Factors of 28: 1 2 4 7 14 28
Total: 6 factor(s)

Enter a positive integer: 37
Factors of 37: 1 37
Total: 2 factor(s)

(37 has exactly two factors — it is a prime number.)

Enter a positive integer: 100
Factors of 100: 1 2 4 5 10 20 25 50 100
Total: 9 factor(s)

Enter a positive integer: 1
Factors of 1: 1
Total: 1 factor(s)

Code Explanation

i * i <= num — the loop bound. This is equivalent to i <= sqrt(num) but avoids floating-point arithmetic. Note: i <= num/i is not equivalent when num is not a perfect square; i*i is the clean approach.
small[] and large[] — two arrays hold the two halves of the divisor pairs. small[] holds the divisors found by the loop (≤ √num), large[] holds their paired partners (≥ √num). Both arrays are fixed at 600 elements, which is more than enough: the maximum number of divisors for any number up to 1,000,000 is 240.
if (i != num / i) — prevents storing a divisor twice when num is a perfect square. For n = 36 and i = 6: 36/6 = 6 = i, so large[] does not get a duplicate entry.
Printing in sorted order — small[] is already in ascending order (the loop increments i). large[] is collected in ascending order but printed in reverse (j = lc-1 down to 0), giving the larger factors in ascending order after the smaller ones.
sc + lc — the total factor count. For a prime like 37: sc = 2 (stores 1 and 37), lc = 0 (since 37/1 = 37 = num, the pair equals i=1’s partner, but i=1 and num/i=37; since 1 ≠ 37, lc gets 37 stored… let me re-check). Actually: for i=1, small[sc++]=1; i != num/i (1 != 37), so large[lc++]=37. For i=6: 6*6=36 <= 37? No. So the loop ends. sc=1, lc=1, total=2. Output: small: 1, large reversed: 37. ✓

Factor Count Patterns

Number	Factors	Count	Property
1	1	1	unit
7	1, 7	2	prime
9	1, 3, 9	3	perfect square of prime
12	1, 2, 3, 4, 6, 12	6	highly composite
36	1, 2, 3, 4, 6, 9, 12, 18, 36	9	perfect square (odd count)
48	1, 2, 3, 4, 6, 8, 12, 16, 24, 48	10	—

A perfect square always has an odd number of factors — the square root counts once, all other divisors come in pairs.

What This Program Teaches

The paired-divisor trick — every divisor i ≤ √n has a partner n/i ≥ √n. Collecting both in one loop halves the work and is used in perfect number, prime factorization, and totient function programs.
O(√n) complexity — choosing the right loop bound transforms a program from unusably slow for large inputs into instantaneous. For n = 10⁶: O(n) = 1,000,000 iterations, O(√n) = 1,000 iterations.
Sorted output from two arrays — collecting small and large divisors separately and printing large in reverse is a simple way to produce sorted output without a sort algorithm.
Detecting primes via factor count — any number with exactly 2 factors is prime. This turns the factors program into a primality test.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

Print Factors of a Number in C – O(√n) Algorithm