Factores primos distintos de un número dado N

Dado un número N , la tarea es encontrar los factores primos distintos de N .

Ejemplos:

Entrada: N = 12
Salida: 2 3
Explicación: Los factores de 12 son 1, 2, 3, 4, 6, 12.
Entre estos, los distintos factores primos son 2 y 3.

Entrada: N = 39
Salida: 3 13

Enfoque: El enfoque es utilizar un mapa para verificar si un factor dado del número ha ocurrido antes o no. Ahora siga los pasos a continuación para resolver este problema:

1. Cree un mapa visitado para realizar un seguimiento de todos los factores primos anteriores.
2. Cree una variable C e inicialícela con 2.
3. Mientras que N es divisible por C , imprima C si C no está presente en el mapa. Ahora divide N por C. También incrementa C en 1.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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.

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

3 13 

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(N ^1/2 )

Enfoque eficiente: este enfoque es similar al enfoque anterior donde encontramos factores primos. La única diferencia es que pasamos de 2 a sqrt(n) para encontrar todos los factores primos, ya que sabemos que eso también es suficiente para verificar los números primos. Si aún se encuentra que el número es mayor que 2, entonces es primo y también debemos imprimirlo.

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

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

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

Complejidad de tiempo: O(N^(1/2))

Espacio auxiliar: O(N^(1/2))