Prime Factors of a Number - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a positive integer n, your task is to find all its prime factors. Prime factors are the prime numbers that multiply together to give the original number.

For example, the prime factors of 60 are 2, 2, 3, and 5.

Examples❯

n Output Description
60 2, 2, 3, 5 60 is divisible by 2 (twice), then 3, then 5
97 97 97 is a prime number, so only itself is a prime factor
100 2, 2, 5, 5 100 = 2×2×5×5, so these are the prime factors
1 [] 1 has no prime factors by definition
0 [] Prime factorization is undefined for 0
"" [] Empty input is treated as 0; no prime factors
2 2 Smallest prime number; itself is the only prime factor
84 2, 2, 3, 7 84 = 2×2×3×7, step-by-step trial division reveals this
121 11, 11 121 is 11 squared; 11 is a prime
7919 7919 A large prime number; only factor is itself

Solution❯

Understanding the Problem

We are given a positive integer n, and we need to find all of its prime factors. A prime factor is a prime number that divides the number exactly, without leaving a remainder.

For example, take n = 60. Its prime factorization is:

60 = 2 × 2 × 3 × 5. So the prime factors are 2, 2, 3, 5.

Our goal is to write a program that outputs all these prime factors step by step in the correct order.

Step-by-Step Solution with Example

Step 1: Handle all 2s (even factors)

Since 2 is the only even prime number, we first check if the number n is divisible by 2.

While it is divisible, we keep dividing it by 2 and print 2 each time. This step removes all even factors from n.

Example: If n = 60, we divide by 2 repeatedly:

  • 60 ÷ 2 = 30 → print 2
  • 30 ÷ 2 = 15 → print 2
  • 15 is not divisible by 2 → stop

Step 2: Check odd numbers up to √n

Now we check for odd factors starting from 3 up to the square root of the current value of n. We increase the divisor by 2 each time (i.e., 3, 5, 7, ...).

Each time n is divisible by the current divisor, we print the divisor and divide n repeatedly until it is no longer divisible by that number.

Continuing the example: Now n = 15

  • 3 divides 15 → print 3
  • 15 ÷ 3 = 5
  • 3 doesn’t divide 5 → move to next
  • 5 divides 5 → print 5
  • 5 ÷ 5 = 1 → done

Step 3: Check if anything is left

At this point, if n is still greater than 2, it means it is a prime number itself and should be printed.

In our example, after dividing by 5, n becomes 1, so nothing more to print.

Edge Cases

  • n = 1: There are no prime factors. Output should be empty.
  • n is a prime number (e.g., 13): It is only divisible by 1 and itself. So we directly print the number once.
  • n is a power of a prime (e.g., 24 = 16): We keep printing the same prime multiple times.
  • Very large n: The algorithm works efficiently since it only loops till √n, and we skip all even numbers after handling 2.

Final Thoughts

This method is both intuitive and efficient for beginners. We break the problem into small understandable steps: handle even factors first, then odd factors, and finally check if anything is left.

We also considered common edge cases like 1, prime numbers, and large values of n.

By using trial division smartly — especially skipping even numbers — the algorithm remains simple yet powerful for a wide range of inputs.

Algorithm Steps❯

  1. Divide n by 2 until it's no longer divisible, printing 2 each time. This handles all even factors.
  2. Loop from 3 up to the square root of n, checking only odd numbers:
    • If n is divisible by i, print i and divide n repeatedly by i.
  3. If n is still greater than 2 at the end, it is a prime number and should be printed.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <math.h>

void primeFactors(int n) {
    while (n % 2 == 0) {
        printf("2 ");
        n /= 2;
    }
    for (int i = 3; i <= (int)sqrt(n); i += 2) {
        while (n % i == 0) {
            printf("%d ", i);
            n /= i;
        }
    }
    if (n > 2) {
        printf("%d", n);
    }
    printf("\n");
}

int main() {
    int number = 60;
    printf("Prime factors of %d are: ", number);
    primeFactors(number);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(log n)If the number is a power of 2 (e.g., 2, 4, 8, 16...), we repeatedly divide by 2, which takes log₂(n) steps.
Average CaseO(√n)We check for divisibility from 2 up to √n. Each time we divide out a factor completely before continuing, which ensures no repeated work. This is efficient for most values of n.
Worst CaseO(√n)In the worst case (e.g., when n is a large prime), we must try all numbers up to √n to determine that it has no smaller prime factor.

Space Complexity❯

O(1)

Explanation: The algorithm uses a constant amount of space to store the loop variable and the input value n. All factorization is done in-place without additional data structures.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...