Data Modelling & AI Data Structure & Algorithm

Distinct Prime Factors of a given number N

23 June 2025

0

Given a number N, the task is to find the distinct Prime Factors of N.

Examples:

Input: N = 12
Output: 2 3
Explanation: The factors of 12 are 1, 2, 3, 4, 6, 12.
Among these the distinct prime factors are 2 and 3.

Input: N = 39
Output: 3 13

Approach: The approach is to use a map to check whether a given factor of the number has occurred earlier or not. Now follow the below steps to solve this problem:

Create a map visited to keep track of all previous prime factors.
Create a variable C, and initialize it with 2.
While N is divisible by C, print C if C is not present in the map. Now divide N by C. Also increment C by 1.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find distinct prime factor
// of a number N
void distinctPrimeFactors(int N)
{
    if (N < 2) {
        cout << -1;
    }
 
    int c = 2;
    unordered_map<int, bool> visited;
 
    while (N > 1) {
        if (N % c == 0) {
            if (!visited) {
                cout << c << " ";
                visited = 1;
            }
            N /= c;
        }
        else
            c++;
    }
}
 
// Driver Code
int main()
{
    int N = 39;
    distinctPrimeFactors(N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Function to find distinct prime factor
  // of a number N
  static void distinctPrimeFactors(int N)
  {
    if (N < 2) {
      System.out.print(-1);
    }
 
    int c = 2;
 
    // Create a new dictionary of
    // strings, with string keys.
    HashMap<Integer, Boolean> visited = new HashMap<>();
 
    for(int i = 0; i < N; i++) {
      visited.put(i, false);
    }
 
    while (N > 1) {
      if (N % c == 0) {
        if(visited.containsKey(c)){
          if (!visited.get(c)) {
            System.out.print(c + " ");
            visited.put(c, true);
          }
        }
        N /= c;
      }
      else
        c++;
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 39;
    distinctPrimeFactors(N);
  }
}
 
// This code is contributed by Samim Hossain Mondal

Python3

# python3 program for the above approach
 
# Function to find distinct prime factor
# of a number N
def distinctPrimeFactors(N):
 
    if (N < 2):
        print(-1)
 
    c = 2
    visited = {}
 
    while (N > 1):
        if (N % c == 0):
            if (not c in visited):
                print(c, end=" ")
                visited = 1 if c in visited else 0
 
            N //= c
 
        else:
            c += 1
 
# Driver Code
if __name__ == "__main__":
 
    N = 39
    distinctPrimeFactors(N)
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find distinct prime factor
  // of a number N
  static void distinctPrimeFactors(int N)
  {
    if (N < 2) {
      Console.Write(-1);
    }
 
    int c = 2;
 
    // Create a new dictionary of
    // strings, with string keys.
    Dictionary<int, bool> visited =
      new Dictionary<int, bool>();
 
    for(int i = 0; i < N; i++) {
      visited[i] = false;
    }
 
    while (N > 1) {
      if (N % c == 0) {
        if(visited.ContainsKey(c)){
          if (!visited) {
            Console.Write(c + " ");
            visited = true;
          }
        }
        N /= c;
      }
      else
        c++;
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 39;
    distinctPrimeFactors(N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find distinct prime factor
    // of a number N
    const distinctPrimeFactors = (N) => {
        if (N < 2) {
            document.write(-1);
        }
 
        let c = 2;
        let visited = {};
 
        while (N > 1) {
            if (N % c == 0) {
                if (!(c in visited)) {
                    document.write(`${c} `);
                    visited = 1;
                }
                N = parseInt(N / c);
            }
            else
                c++;
        }
    }
 
    // Driver Code
 
    let N = 39;
    distinctPrimeFactors(N);
 
// This code is contributed by rakeshsahni
 
</script>

Output

3 13

Time Complexity: O(N)
Auxiliary Space: O(N^1/2)

Efficient Approach: This approach is similar to above approach where we find prime factors. The only difference is that we traverse from 2 to sqrt(n) to find all prime factors since we know that is sufficient for checking for prime numbers as well. If the number is still found to be greater than 2 then it is prime and we need to print it as well.

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find distinct prime factor
// of a number N
void distinctPrimeFactors(int N)
{
    if (N < 2) {
        cout << -1;
        return;
    }
    if (N == 2) {
        cout << 2;
        return;
    }
 
    unordered_map<int, bool> visited;
 
    for (int i = 2; i * i <= N; i++) {
        while (N % i == 0) {
            if (!visited[i]) {
                cout << i << " ";
                visited[i] = 1;
            }
            N /= i;
        }
    }
    if (N > 2)
        cout << N;
}
 
// Driver Code
int main()
{
    int N = 315;
    distinctPrimeFactors(N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG 
{
  // Function to find distinct prime factor
  // of a number N
  static void distinctPrimeFactors(int N)
  {
    if (N < 2) {
      System.out.print(-1);
      return;
    }
    if (N == 2) {
      System.out.print(2);
      return;
    }
    HashMap<Integer, Boolean> visited = new HashMap<>();
    for (int i = 2; i * i <= N; i++) {
      while (N % i == 0) {
        if (!visited.containsKey(i)) {
          System.out.print(i + " ");
          visited.put(i, true);
        }
        N /= i;
      }
    }
    if (N > 2) {
      System.out.print(N);
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 315;
    distinctPrimeFactors(N);
  }
}
 
// This code is contributed by Taranpreet

Python3

# Python program for the above approach
 
# Function to find distinct prime factor
# of a number N
def distinctPrimeFactors(N):
     
    if (N < 2):
        print(-1)
        return
    if N == 2:
      print(2)
      return
    visited = {}
     
    i = 2
    while(i * i <= N):
        while(N % i == 0):
            if(i not in visited):
                print(i , end = " ")
                visited[i] = 1
                 
            N //= i
        i+=1
             
    if(N > 2):
        print(N)
 
# Driver Code
N = 315
distinctPrimeFactors(N);
 
# This code is contributed by Shubham Singh

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
   
  // Function to find distinct prime factor
  // of a number N
  static void distinctPrimeFactors(int N)
  {
    if (N < 2) {
      Console.Write(-1);
      return;
    }
    if (N == 2) {
      Console.Write(2);
      return;
    }
    Dictionary<int, bool> visited =
      new Dictionary<int, bool>();
 
    for (int i = 2; i * i <= N; i++) {
      while (N % i == 0) {
        if (!visited.ContainsKey(i)) {
          Console.Write(i + " ");
          visited[i] =  true;
        }
        N /= i;
      }
    }
    if (N > 2) {
      Console.Write(N);
    }
  }
       
  // Driver code
  public static void Main()
  {
    int N = 315;
    distinctPrimeFactors(N);
  }
}
 
// This code is contributed by avijitmondal1998

Javascript

<script>
// Javascript program for the above approach
 
// Function to find distinct prime factor
// of a number N
function distinctPrimeFactors(N)
{
    if (N < 2) {
        document.write(-1);
        return;
    }
     
    if (N === 2) {
        document.write(2);
        return;
    }
    visited = {};
     
    for(var i = 2; i * i <= N; i++)
    {
        while(N % i == 0)
        {
            if(!visited[i])
            {
                document.write(i + " ");
                visited[i] = 1;
            }
            N /= i;
        }
    }
    if(N > 2)
    document.write(N);
}
 
// Driver Code
var N = 315;
distinctPrimeFactors(N);
 
// This code is contributed by Shubham Singh
</script>

Output

3 5 7

Time Complexity: O(N^(1/2))
Auxiliary Space: O(N^(1/2))

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Distinct Prime Factors of a given number N

C++

Java

Python3

C#

Javascript

C++14

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

It’s your last chance to score a $50 Samsung credit before tomorrow’s big product announcement

EDITOR PICKS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR POSTS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR CATEGORY

ABOUT US

FOLLOW US