Find Factors of a Number in C, C++, Java and Python

Every positive integer n has at least two factors (1 and itself); placement coding rounds ask for all of them, printed in O(√n) time.

The standard version of the question accepts output in any order, handles inputs up to 10^6 or larger, and times out brute-force solutions on hidden test cases. Two approaches cover both correctness and performance. All four language implementations follow the same logic; the per-language notes below call out only the differences that matter.

What Is a Factor

A factor of n is any positive integer that divides n with zero remainder. Formally, i is a factor of n if n % i == 0.

Three examples to anchor the definition:

• Factors of 12: 1, 2, 3, 4, 6, 12 — six factors total.
• Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 — nine factors total.
• Factors of 7 (prime): 1, 7 — the minimum for any positive integer.

The factor relationship is symmetric: if 3 divides 12 exactly, then 12/3 = 4 also divides 12 exactly. This pairing property drives the optimised algorithm.

Brute-Force Approach: O(n)

The naive approach checks every integer from 1 to n.

Algorithm

• For i from 1 to n (inclusive):
  • If n % i == 0, print i.

C (Brute Force)

#include <stdio.h>

void findFactors(int n) {
    printf("Factors of %d: ", n);
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            printf("%d ", i);
        }
    }
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    findFactors(num);
    return 0;
}

This works correctly. For small inputs it is fast enough. For n = 10^6, the loop runs 10^6 iterations; for n = 10^9, it runs 10^9 iterations, which exceeds the one-second time limit typical of AMCAT and TCS NQT online judges.

Optimised Approach: O(√n)

The key observation: factors come in pairs. If i divides n, then n/i also divides n. Both can be printed from a single divisibility check. The loop only needs to run from 1 to √n to catch every pair.

Why i * i <= n beats i <= sqrt(n)

Using i <= sqrt(n) as the loop condition introduces floating-point risk. The cppreference documentation for sqrt notes that the result is the nearest representable floating-point value, not an exact integer. For a perfect square like n = 36, sqrt(36.0) may return 5.9999 on some implementations. That causes the loop to exit before checking i = 6 and misses the factor pair (6, 36/6). The condition i * i <= n uses integer arithmetic throughout: no floating-point, no rounding risk.

Handling Perfect Squares

When i * i == n, i and n/i are the same value. Printing both would duplicate the output. The check if i != n / i suppresses the second print for that case.

For n = 36 at i = 6: i * i = 36 = n, so i == n / i is true, and only one 6 is printed.

Algorithm

• For i from 1 while i * i <= n:
  • If n % i == 0:
    • Print i.
    • If i != n / i, print n/i as well.

This finds all factor pairs in O(√n) iterations.

Code in C, C++, Java, and Python

C

#include <stdio.h>

void findFactors(int n) {
    printf("Factors of %d: ", n);
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            printf("%d ", i);
            if (i != n / i) {
                printf("%d ", n / i);
            }
        }
    }
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    findFactors(num);
    return 0;
}

C++

#include <iostream>
using namespace std;

void findFactors(int n) {
    cout << "Factors of " << n << ": ";
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
            if (i != n / i) {
                cout << n / i << " ";
            }
        }
    }
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    findFactors(num);
    return 0;
}

The C++ version uses cin and cout in place of scanf/printf. The loop logic is identical to the C version.

Java

import java.util.Scanner;

public class FactorFinder {
    public static void findFactors(int n) {
        System.out.print("Factors of " + n + ": ");
        for (int i = 1; (long) i * i <= n; i++) {
            if (n % i == 0) {
                System.out.print(i + " ");
                if (i != n / i) {
                    System.out.print(n / i + " ");
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();
        findFactors(num);
        sc.close();
    }
}

The Java version casts to (long) i * i to prevent integer overflow. For values of i near Integer.MAX_VALUE, the product i * i overflows to a negative number under 32-bit arithmetic, breaking the loop condition. The cast widens the multiplication to 64-bit before it happens.

Python

import math

def find_factors(n):
    print(f"Factors of {n}: ", end="")
    i = 1
    while i * i <= n:
        if n % i == 0:
            print(i, end=" ")
            if i != n // i:
                print(n // i, end=" ")
        i += 1

num = int(input("Enter a number: "))
find_factors(num)

Python’s // operator performs integer division, matching the C/Java behaviour on non-negative integers. The Python docs for math.isqrt offer an alternative loop bound: while i <= math.isqrt(n). This computes the exact integer square root without any floating-point conversion, making the intent explicit when reading the code.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Iterations (n = 10^6)
Brute force (1 to n)	O(n)	O(1)	1,000,000
Optimised (1 to √n)	O(√n)	O(1)	1,000

Both approaches use constant extra space: no arrays, no hash maps, just two loop variables. Storing the results in a list would add O(d(n)) space where d(n) is the count of divisors, which grows slowly relative to n.

The table makes the practical gap concrete. For n = 10^9, the brute-force approach is impractical within a one-second time limit; the optimised loop completes in roughly 31600 iterations.

How This Appears in Placement Tests

Factor-finding shows up in three forms in the coding rounds used by Indian recruitment pipelines:

• Direct question: Print all factors of n in ascending order. The expected solution is the O(√n) approach. Brute force may pass for small n but times out on hidden test cases with large inputs.
• Divisibility sub-problem: GCD, LCM, and prime-factorisation questions all use factor-finding as an internal step. Articulating “I loop to √n and pair each factor with its complement” covers all three variants.
• Count variant: Count the number of divisors of n. The same O(√n) loop counts pairs, with special handling for perfect squares (count 1 instead of 2 when i == n / i).

AMCAT Automata and TCS NQT both include divisibility-based problems in their coding sections. Students who understand the O(√n) pattern and the perfect-square edge case are well-prepared. Stating the time complexity clearly rounds out the expected answer.

For broader DSA interview preparation, FACE Prep maintains a curated list covering trees, graphs, strings, and number theory questions. Both the palindrome check and finding the minimum and maximum in a single pass use the same one-loop, two-results-per-pass pattern as the factor algorithm.

The pairing instinct behind O(√n) shows up beyond algorithms. Batching LLM API calls reduces per-request overhead in the same way that pairing factors reduces iterations. TinkerLLM is where that cost-aware thinking becomes practical at ₹299, with real API calls and measurable results in the dashboard.