Prime Factors of a Number: flowchart, algorithm and program

This program reads a number n and prints its prime factors in increasing order, so 12 gives 2 2 3. It starts with i = 2 and keeps dividing n by i while it divides evenly, then moves on to the next i until n becomes 1.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Set i = 2.
  4. Step 4: If n > 1, go to step 5; otherwise go to step 9.
  5. Step 5: If n % i == 0, go to step 6; otherwise go to step 8.
  6. Step 6: Print i.
  7. Step 7: Set n = n / i. Go to step 5.
  8. Step 8: Increase i by 1. Go to step 4.
  9. Step 9: Print newline.
  10. Step 10: Stop.

Pseudocode

BEGIN
    READ n
    i ← 2
    WHILE n > 1 DO
        WHILE n % i == 0 DO
            PRINT i
            n ← n / i
        END WHILE
        i++
    END WHILE
    PRINT newline
END

Program in C, Python and Java

Prime Factors of a Number program in C

#include <stdio.h>

int main() {
    int n, i;
    printf("Enter n: ");
    scanf("%d", &n);
    i = 2;
    while (n > 1) {
        while (n % i == 0) {
            printf("%d ", i);
            n = n / i;
        }
        i++;
    }
    printf("\n");
    return 0;
}

Prime Factors of a Number program in Python

n = int(input("Enter n: "))
i = 2
result = []
while n > 1:
    while n % i == 0:
        result.append(str(i))
        n = n // i
    i += 1
print(" ".join(result))

Prime Factors of a Number program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        int i = 2;
        while (n > 1) {
            while (n % i == 0) {
                System.out.print(i + " ");
                n = n / i;
            }
            i++;
        }
        System.out.println();
    }
}

Sample input: n = 12
Output: 2 2 3

How it works

  • Start with i = 2, the smallest possible prime factor. The outer loop `while (n > 1)` runs until n has been fully divided down to 1.
  • The inner loop `while (n % i == 0)` checks if i divides n exactly. If it does, print i and replace n with `n / i`. This repeats, so a factor like 2 in 12 is printed twice.
  • When i no longer divides n, `i++` moves to the next candidate. No separate prime check is needed: by the time i reaches a composite number, its smaller prime factors have already been divided out of n, so it can never divide n.
  • For n = 12: i = 2 divides 12 to give 6, then 3, so it prints 2 2 and n becomes 3. i becomes 3, which divides 3 once to give n = 1, so it prints 3. The loop ends with the output 2 2 3.

Dry run (trace table)

StepLineBoxniOutput
13Start
26Read n12Enter n:
37i = 2122
48n > 1?122
59n % i == 0?122
610Print i1222
711n = n / i62
89n % i == 0?62
910Print i622
1011n = n / i32
119n % i == 0?32
1213i++33
138n > 1?33
149n % i == 0?33
1510Print i333
1611n = n / i13
179n % i == 0?13
1813i++14
198n > 1?14
2015Print newline14

Time and space complexity

Time: O(n) · Space: O(1). In the worst case (n prime) i increases up to n with constant work per step, and only a few variables are used.

Common mistakes

  • Using `if` instead of the inner `while`, which prints a repeated factor like 2 only once and leaves wrong results for numbers such as 12 or 8.
  • Forgetting `i++` after the inner loop, or putting it inside the inner loop, which causes an infinite loop or skips factors.
  • Not handling n = 1 or n less than 2: the loop never runs, so nothing is printed. This is correct, but students often expect some output.

Viva questions

Q1. Why does the variable i start at 2 and not at 0 or 1?

The smallest prime is 2. Starting at 0 would cause a divide-by-zero in n % i, and starting at 1 would loop forever because 1 divides every n without reducing it.

Q2. What is the purpose of the inner while loop on line 9? Why not just use an if?

A prime factor can appear several times, like 2 in 12 = 2*2*3. The inner loop keeps dividing by i until it no longer divides n, so every repeated factor is printed. An if would print it only once.

Q3. Why is it guaranteed that i is always prime when it divides n, even though we never check that i is prime?

We divide out all smaller factors before moving to a larger i. So by the time i reaches a composite number, its prime factors have already been removed from n and it cannot divide n.

Q4. What does the program print for n = 12? Trace the values of n and i.

It prints 2 2 3. With i=2, n goes 12 to 6 to 3. Then i becomes 3, 3 divides n, and n becomes 1. The outer loop ends.

Q5. What happens if the user enters 1, 0 or a negative number?

For 1, 0 or any negative n, the condition n > 1 is false at the start. The program prints only a newline and no factors. It does not crash, but it also gives no message for invalid input.

Q6. What is the condition n > 1 on the outer loop checking?

It checks whether any prime factors are still left. When n has been fully divided down to 1, every factor has been printed, so the loop stops.

Q7. What is the time complexity of this program?

In the worst case n is prime, so i goes from 2 up to n. That makes it O(n). If the loop stopped at i*i > n and printed the leftover n, it would be O(sqrt(n)).

Q8. What would you change to make this faster, and what extra step would that need?

Run the outer loop while i * i <= n, which gives O(sqrt(n)). After the loop, if n > 1 the leftover n is itself a prime factor, so print it.

Frequently asked questions

Why don't we need to check whether i is prime?

Every smaller prime factor has already been divided out of n before i reaches a composite number. So a composite i can never divide the remaining n.

What is the time complexity of this program?

In the worst case, when n is prime, i goes up to n, so it is O(n). Stopping the loop at the square root of n and printing any leftover n > 1 makes it O(√n).

Why does the output print 2 twice for 12?

Because 12 = 2 × 2 × 3. The inner while loop keeps dividing by 2 while n % 2 == 0, printing 2 each time, before i moves on to 3.

More programs

← All programs

Try AI Flowchart free →