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
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 2.
- Step 4: If n > 1, go to step 5; otherwise go to step 9.
- Step 5: If n % i == 0, go to step 6; otherwise go to step 8.
- Step 6: Print i.
- Step 7: Set n = n / i. Go to step 5.
- Step 8: Increase i by 1. Go to step 4.
- Step 9: Print newline.
- 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)
| Step | Line | Box | n | i | Output |
|---|---|---|---|---|---|
| 1 | 3 | Start | |||
| 2 | 6 | Read n | 12 | Enter n: | |
| 3 | 7 | i = 2 | 12 | 2 | |
| 4 | 8 | n > 1? | 12 | 2 | |
| 5 | 9 | n % i == 0? | 12 | 2 | |
| 6 | 10 | Print i | 12 | 2 | 2 |
| 7 | 11 | n = n / i | 6 | 2 | |
| 8 | 9 | n % i == 0? | 6 | 2 | |
| 9 | 10 | Print i | 6 | 2 | 2 |
| 10 | 11 | n = n / i | 3 | 2 | |
| 11 | 9 | n % i == 0? | 3 | 2 | |
| 12 | 13 | i++ | 3 | 3 | |
| 13 | 8 | n > 1? | 3 | 3 | |
| 14 | 9 | n % i == 0? | 3 | 3 | |
| 15 | 10 | Print i | 3 | 3 | 3 |
| 16 | 11 | n = n / i | 1 | 3 | |
| 17 | 9 | n % i == 0? | 1 | 3 | |
| 18 | 13 | i++ | 1 | 4 | |
| 19 | 8 | n > 1? | 1 | 4 | |
| 20 | 15 | Print newline | 1 | 4 |
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.