Prime Factors of a Number

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.

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., 2⁴ = 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.

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.

#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;
}

#include <iostream>
#include <cmath>
using namespace std;

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

int main() {
    int number = 60;
    cout << "Prime factors of " << number << " are: ";
    primeFactors(number);
    return 0;
}

def prime_factors(n):
    while n % 2 == 0:
        print(2, end=' ')
        n //= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            print(i, end=' ')
            n //= i
        i += 2
    if n > 2:
        print(n)

number = 60
print(f"Prime factors of {number} are:", end=' ')
prime_factors(number)

public class PrimeFactors {
    public static void primeFactors(int n) {
        while (n % 2 == 0) {
            System.out.print(2 + " ");
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                System.out.print(i + " ");
                n /= i;
            }
        }
        if (n > 2) {
            System.out.print(n);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int number = 60;
        System.out.print("Prime factors of " + number + " are: ");
        primeFactors(number);
    }
}

function primeFactors(n) {
    while (n % 2 === 0) {
        process.stdout.write('2 ');
        n /= 2;
    }
    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i === 0) {
            process.stdout.write(i + ' ');
            n /= i;
        }
    }
    if (n > 2) {
        process.stdout.write(n.toString());
    }
    process.stdout.write('\n');
}

const number = 60;
process.stdout.write(`Prime factors of ${number} are: `);
primeFactors(number);

package main

import (
    "fmt"
    "math"
)

func primeFactors(n int) {
    for n%2 == 0 {
        fmt.Print(2, " ")
        n /= 2
    }
    for i := 3; i <= int(math.Sqrt(float64(n))); i += 2 {
        for n%i == 0 {
            fmt.Print(i, " ")
            n /= i
        }
    }
    if n > 2 {
        fmt.Print(n)
    }
    fmt.Println()
}

func main() {
    number := 60
    fmt.Printf("Prime factors of %d are: ", number)
    primeFactors(number)
}

fn prime_factors(mut n: u32) {
    while n % 2 == 0 {
        print!("2 ");
        n /= 2;
    }
    let mut i = 3;
    while i * i <= n {
        while n % i == 0 {
            print!("{} ", i);
            n /= i;
        }
        i += 2;
    }
    if n > 2 {
        print!("{}", n);
    }
    println!();
}

fn main() {
    let number = 60;
    print!("Prime factors of {} are: ", number);
    prime_factors(number);
}

fun primeFactors(n: Int) {
    var number = n
    while (number % 2 == 0) {
        print("2 ")
        number /= 2
    }
    var i = 3
    while (i * i <= number) {
        while (number % i == 0) {
            print("$i ")
            number /= i
        }
        i += 2
    }
    if (number > 2) {
        print(number)
    }
    println()
}

fun main() {
    val number = 60
    print("Prime factors of $number are: ")
    primeFactors(number)
}

func primeFactors(_ n: Int) {
    var number = n
    while number % 2 == 0 {
        print("2", terminator: " ")
        number /= 2
    }
    var i = 3
    while i * i <= number {
        while number % i == 0 {
            print(i, terminator: " ")
            number /= i
        }
        i += 2
    }
    if number > 2 {
        print(number)
    }
    print()
}

let number = 60
print("Prime factors of \(number) are:", terminator: " ")
primeFactors(number)

function primeFactors(n: number): void {
    while (n % 2 === 0) {
        process.stdout.write('2 ');
        n /= 2;
    }
    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i === 0) {
            process.stdout.write(i + ' ');
            n /= i;
        }
    }
    if (n > 2) {
        process.stdout.write(n.toString());
    }
    process.stdout.write('\n');
}

const number = 60;
process.stdout.write(`Prime factors of ${number} are: `);
primeFactors(number);

Time complexity

Space complexity

O(1)

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.