Distinct Prime Factors of a given number N

0 0 5 minutes read

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 zambiatek!