Prime factors of a number

Last Updated : 03 Oct, 2025

Given a number n, find all prime factors of n.
Note : Prime number is a natural number greater than 1 that has exactly two factors:1 and itself.

Examples:

Input: n = 18
Output: [2, 3, 3]
Explanation: The prime factorization of 18 is 2×3².
Input: n = 25
Output: [5, 5]
Explanation: The prime factorization of 25 is 5².

Table of Content

[Naive Approach] Iterative Time O(n) and space O(1)
[Expected Approach] Prime Factorisation Time O(sqrt(n)) and Space (1)

[Naive Approach] Iterative Time O(n) and space O(1)

Step by Step implementation:

Start a loop from i = 2 up to n.
For each i, check if n is divisible by i (i.e n % i == 0).
While n is divisible by i, store i as a factor and divide n by i.
Continue this process for all i up to n to extract all prime factors.

C++

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

vector<int> primeFactor (int n ){
    vector<int> ans ;
    for (int i = 2 ; i <= n ; i++){
        
        // n %  i  == 0 means n is divisible by i 
        while (n % i == 0 && n > 0 ){
            ans.push_back(i);
            n = n / i ;
        }
    }
    return ans ;
}
int main() {
    int n =  18;
    vector <int> ans = primeFactor(n);
    for (auto x : ans ){
        cout << x  <<' ';
    }
    return 0 ;
}

Java

import java.util.ArrayList;

class GFG {
    public static ArrayList<Integer> primeFactor(int n) {
        ArrayList<Integer> ans = new ArrayList<>();
        
        // Loop from 2 to n
        for (int i = 2; i <= n; i++) {
            
            // n % i == 0 means n is divisible by i
            while (n % i == 0 && n > 0) {
                ans.add(i);
                
                // divide n by i to remove this factor
                n = n / i; 
            }
        }
        return ans;
    }
    
    public static void main (String[] args) {
        int n = 18;
        ArrayList<Integer> ans = primeFactor(n);
 
        for (int x : ans) {
            System.out.print(x + " ");
        }
    }
}

Python

def primeFactor(n):
    ans = []
    
    # Loop from 2 to n
    for i in range(2, n+1):
        
        # n % i == 0 means n is divisible by i
        while n % i == 0 and n > 0:
            ans.append(i) 
            
             # divide n by i to remove this factor
            n = n // i
    return ans

if __name__ == "__main__":    

    n = 18
    ans = primeFactor(n)
    for x in ans:
        print(x, end=' ')

using System;
using System.Collections.Generic;

class GFG {
   
    static List<int> primeFactor(int n) {
        List<int> ans = new List<int>();
        
        // Loop from 2 to n
        for (int i = 2; i <= n; i++) {
            
            // n % i == 0 means n is divisible by i
            while (n % i == 0 && n > 0) {
                ans.Add(i); 
                
                // divide n by i to remove this factor
                n = n / i; 
            }
        }
        return ans;
    }
    
    static void Main() {
        int n = 18;
        List<int> ans = primeFactor(n);
        foreach (int x in ans) {
            Console.Write(x + " ");
        }
    }
}

JavaScript

function primeFactor(n) {
    let ans = [];
    
    // Loop from 2 to n
    for (let i = 2; i <= n; i++) {
        
        // n % i == 0 means n is divisible by i
        while (n % i === 0 && n > 0) {
            ans.push(i); 
            
            // divide n by i to remove this factor
            n = n / i; 
        }
    }
    return ans;
}

//Driver Code 

let n = 18;
let ans = primeFactor(n);
for (let x of ans) {
    process.stdout.write(x + ' ');
}

Output

2 3 3

[Expected Approach] Prime Factorisation Time O(sqrt(n)) and Space (1)

Every composite number has at least one prime factor less than or equal to its square root. This property can be proved using a counter statement -

Let a and b be two factors of n such that a*b = n.
If both are greater than sqrt(n), a*b > sqrt(n)*sqrt(n), which contradicts the expression a * b = n

Step by Step implementation

While n is divisible by 2, print 2 and divide n by 2.
After step 1, n must be odd. Now start a loop from i = 3 to the square root of n. While i divides n, print i, and divide n by i. After i fails to divide n, increment i by 2 because next prime factor will also be odd since we have already taken care of all the 2 and continue.
If n greater than 2, then n is the last prime factor.

C++

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

vector<int> primeFactors(int n) {
    vector<int> factors;

    // Store the number of 2s that divide n
    while (n % 2 == 0) {
        factors.push_back(2);
        n = n / 2;
    }

    // n must be odd at this point. So we can 
     // skip one element (i = i + 2)
    for (int i = 3; i * i <= n; i = i + 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n = n / i;
        }
    }

    // If n is a prime number greater than 2
    if (n > 2)
        factors.push_back(n);

    return factors;
}

int main() {
    int n = 18;
    vector<int> ans = primeFactors(n);

    // Print the factors stored in vector
    for (int factor : ans) {
        cout << factor << " ";
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

// A function to return all prime factors of a given number n
int primeFactors(int n, int **factors) {
    *factors = (int *)malloc(sizeof(int) * 10000); // allocate memory
    int index = 0;

    // Store the number of 2s that divide n
    while (n % 2 == 0) {
        (*factors)[index++] = 2;
        n = n / 2;
    }

    // n must be odd at this point. So we can 
    // skip one element (i = i + 2)
    for (int i = 3; i * i <= n; i = i + 2) {
        while (n % i == 0) {
            (*factors)[index++] = i;
            n = n / i;
        }
    }

    // If n is a prime number greater than 2
    if (n > 2)
        (*factors)[index++] = n;
        
    // return number of factors stored
    return index; 
}

int main() {
    int n = 18;
    int *ans;
    int size = primeFactors(n, &ans);

    // Print the factors stored in array
    for (int i = 0; i < size; i++) {
        printf("%d ", ans[i]);
    }

    free(ans); // free allocated memory
    return 0;
}

Java

import java.util.ArrayList;

class GfG {

    static ArrayList<Integer> primeFactors(int n) {
        ArrayList<Integer> factors = new ArrayList<>();

        // Store the number of 2s that divide n
        while (n % 2 == 0) {
            factors.add(2);
            n /= 2;
        }

        // n must be odd at this point
        for (int i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }

        // If n is a prime number greater than 2
        if (n > 2)
            factors.add(n);

        return factors;
    }

    public static void main(String[] args) {
        int n = 18;
        ArrayList<Integer> result = primeFactors(n);

        // Printing the factors stored in ArrayList
        for (int factor : result) {
            System.out.print(factor + " ");
        }
    }
}

Python

import math
def primeFactors(n):
    
    # Print the number of two's that divide n
    while n % 2 == 0:
        print 2,
        n = n / 2
        
    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    for i in range(3,int(math.sqrt(n))+1,2):
        
        # while i divides n , print i and divide n
        while n % i== 0:
            print i,
            n = n / i
            
    # Condition if n is a prime
    # number greater than 2
    if n > 2:
        print n
    
if __name__ =="__main__":        
        
    n = 18
    primeFactors(n)

using System;

class GfG {

    static void primeFactors(int n) {

        // Print the number of 2s that divide n
        while (n % 2 == 0) {

            Console.Write(2 + " ");
            n /= 2;
        }

        // n must be odd at this point. So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i * i <= n; i += 2) {

            // While i divides n, print i and divide n
            while (n % i == 0) {

                Console.Write(i + " ");
                n /= i;
            }
        }

        // This condition is to handle the case when
        // n is a prime number greater than 2
        if (n > 2)
            Console.Write(n);
    }

    static void Main() {

        int n = 18;
        primeFactors(n);
    }
}

JavaScript

function primeFactors(n) {

    // Print the number of 2s that divide n
    while (n % 2 == 0) {

        console.log(2 + " ");
        n = Math.floor(n / 2);
    }

    // n must be odd at this point.
    // So we can skip one element
    // (Note i = i +2)

    for (let i = 3; i <= Math.floor(Math.sqrt(n));
         i = i + 2) {

        // While i divides n, print i
        // and divide n
        while (n % i == 0) {

            process.stdout.write(i + " ");
            n = Math.floor(n / i);
        }
    }

    // This condition is to handle the
    // case when n is a prime number
    // greater than 2
    if (n > 2)
        process.stdout.write(n + " ");
}

// Driver Code 
let n = 18;
primeFactors(n);