Compruebe si todos los factores primos del número N son únicos o no

Dado un número N. La tarea es verificar si el número dado N tiene factores primos únicos o no. En caso afirmativo, escriba SÍ ; de lo contrario, escriba NO .
Ejemplos: 
 

Entrada: N = 30 
Salida: SI 
Explicación: 
N = 30 = 2*3*5 
Como todos los factores primos de 30 son únicos.
Entrada: N = 100 
Salida: NO 
Explicación: 
N = 100 = 2*2*5*5 
Como todos los factores primos de 100 no son únicos porque 2 y 5 se repiten dos veces. 
 

Acercarse: 
 

1. Encuentre todos los factores primos del número dado N usando la criba de Eratóstenes .
2. Si el producto de todos los factores primos obtenidos es igual a N , entonces todos los factores primos son únicos, así que imprima SÍ.
3. De lo contrario, imprima NO .

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 that returns the all the
// distinct prime factors in a vector
vector<int> primeFactors(int n)
{
    int i, j;
    vector<int> Prime;
 
    // If n is divisible by 2
    if (n % 2 == 0) {
        Prime.push_back(2);
    }
 
    // Divide n till all factors of 2
    while (n % 2 == 0) {
        n = n / 2;
    }
 
    // Check for the prime numbers other
    // than 2
    for (i = 3; i <= sqrt(n); i = i + 2) {
 
        // Store i in Prime[] i is a
        // factor of n
        if (n % i == 0) {
            Prime.push_back(i);
        }
 
        // Divide n till all factors of i
        while (n % i == 0) {
            n = n / i;
        }
    }
 
    // If n is greater than 2, then n is
    // prime number after n divided by
    // all factors
    if (n > 2) {
        Prime.push_back(n);
    }
 
    // Returns the vector Prime
    return Prime;
}
 
// Function that check whether N is the
// product of distinct prime factors
// or not
void checkDistinctPrime(int n)
{
    // Returns the vector to store
    // all the distinct prime factors
    vector<int> Prime = primeFactors(n);
 
    // To find the product of all
    // distinct prime factors
    int product = 1;
 
    // Find the product
    for (auto i : Prime) {
        product *= i;
    }
 
    // If product is equals to N,
    // print YES, else print NO
    if (product == n)
        cout << "YES";
    else
        cout << "NO";
}
 
// Driver Code
int main()
{
    int N = 30;
    checkDistinctPrime(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function that returns the all the
// distinct prime factors in a vector
static Vector<Integer> primeFactors(int n)
{
    int i, j;
    Vector<Integer> Prime = new Vector<Integer>();
  
    // If n is divisible by 2
    if (n % 2 == 0) {
        Prime.add(2);
    }
  
    // Divide n till all factors of 2
    while (n % 2 == 0) {
        n = n / 2;
    }
  
    // Check for the prime numbers other
    // than 2
    for (i = 3; i <= Math.sqrt(n); i = i + 2) {
  
        // Store i in Prime[] i is a
        // factor of n
        if (n % i == 0) {
            Prime.add(i);
        }
  
        // Divide n till all factors of i
        while (n % i == 0) {
            n = n / i;
        }
    }
  
    // If n is greater than 2, then n is
    // prime number after n divided by
    // all factors
    if (n > 2) {
        Prime.add(n);
    }
  
    // Returns the vector Prime
    return Prime;
}
  
// Function that check whether N is the
// product of distinct prime factors
// or not
static void checkDistinctPrime(int n)
{
    // Returns the vector to store
    // all the distinct prime factors
    Vector<Integer> Prime = primeFactors(n);
  
    // To find the product of all
    // distinct prime factors
    int product = 1;
  
    // Find the product
    for (int i : Prime) {
        product *= i;
    }
  
    // If product is equals to N,
    // print YES, else print NO
    if (product == n)
        System.out.print("YES");
    else
        System.out.print("NO");
}
  
// Driver Code
public static void main(String[] args)
{
    int N = 30;
    checkDistinctPrime(N);
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program for the above approach
 
# Function that returns the all the
# distinct prime factors in a vector
def primeFactors(n) :
 
    Prime = [];
 
    # If n is divisible by 2
    if (n % 2 == 0) :
        Prime.append(2);
 
    # Divide n till all factors of 2
    while (n % 2 == 0) :
        n = n // 2;
     
    # Check for the prime numbers other
    # than 2
    for i in range(3, int(n ** (1/2)),2) :
 
        # Store i in Prime[] i is a
        # factor of n
        if (n % i == 0) :
            Prime.append(i);
         
        # Divide n till all factors of i
        while (n % i == 0) :
            n = n // i;
 
    # If n is greater than 2, then n is
    # prime number after n divided by
    # all factors
    if (n > 2) :
        Prime.append(n);
 
    # Returns the vector Prime
    return Prime;
 
# Function that check whether N is the
# product of distinct prime factors
# or not
def checkDistinctPrime(n) :
 
    # Returns the vector to store
    # all the distinct prime factors
    Prime = primeFactors(n);
     
    # To find the product of all
    # distinct prime factors
    product = 1;
 
    # Find the product
    for i in Prime :
        product *= i;
 
    # If product is equals to N,
    # print YES, else print NO
    if (product == n) :
        print("YES");
    else :
        print("NO");
 
# Driver Code
if __name__ == "__main__" :
 
    N = 30;
    checkDistinctPrime(N);
 
# This code is contributed by Yash_R

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function that returns the all the
// distinct prime factors in a vector
static List<int> primeFactors(int n)
{
    int i;
    List<int> Prime = new List<int>();
   
    // If n is divisible by 2
    if (n % 2 == 0) {
        Prime.Add(2);
    }
   
    // Divide n till all factors of 2
    while (n % 2 == 0) {
        n = n / 2;
    }
   
    // Check for the prime numbers other
    // than 2
    for (i = 3; i <= Math.Sqrt(n); i = i + 2) {
   
        // Store i in Prime[] i is a
        // factor of n
        if (n % i == 0) {
            Prime.Add(i);
        }
   
        // Divide n till all factors of i
        while (n % i == 0) {
            n = n / i;
        }
    }
   
    // If n is greater than 2, then n is
    // prime number after n divided by
    // all factors
    if (n > 2) {
        Prime.Add(n);
    }
   
    // Returns the vector Prime
    return Prime;
}
   
// Function that check whether N is the
// product of distinct prime factors
// or not
static void checkDistinctPrime(int n)
{
    // Returns the vector to store
    // all the distinct prime factors
    List<int> Prime = primeFactors(n);
   
    // To find the product of all
    // distinct prime factors
    int product = 1;
   
    // Find the product
    foreach (int i in Prime) {
        product *= i;
    }
   
    // If product is equals to N,
    // print YES, else print NO
    if (product == n)
        Console.Write("YES");
    else
        Console.Write("NO");
}
   
// Driver Code
public static void Main(String[] args)
{
    int N = 30;
    checkDistinctPrime(N);
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// JavaScript program for the above approach
 
 
// Function that returns the all the
// distinct prime factors in a vector
function primeFactors(n)
{
    let i, j;
    let Prime = new Array();
 
    // If n is divisible by 2
    if (n % 2 == 0) {
        Prime.push(2);
    }
 
    // Divide n till all factors of 2
    while (n % 2 == 0) {
        n = n / 2;
    }
 
    // Check for the prime numbers other
    // than 2
    for (i = 3; i <= Math.sqrt(n); i = i + 2) {
 
        // Store i in Prime[] i is a
        // factor of n
        if (n % i == 0) {
            Prime.push(i);
        }
 
        // Divide n till all factors of i
        while (n % i == 0) {
            n = n / i;
        }
    }
 
    // If n is greater than 2, then n is
    // prime number after n divided by
    // all factors
    if (n > 2) {
        Prime.push(n);
    }
 
    // Returns the vector Prime
    return Prime;
}
 
// Function that check whether N is the
// product of distinct prime factors
// or not
function checkDistinctPrime(n)
{
    // Returns the vector to store
    // all the distinct prime factors
    let Prime = primeFactors(n);
 
    // To find the product of all
    // distinct prime factors
    let product = 1;
 
    // Find the product
    for (let i of Prime) {
        product *= i;
    }
 
    // If product is equals to N,
    // print YES, else print NO
    if (product == n)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver Code
 
let N = 30;
checkDistinctPrime(N);
 
 
// This code is contributed by gfgking
 
</script>

YES

Complejidad de tiempo: O(N*log(log N)), donde N es el número dado.

Espacio auxiliar: O(sqrt(n))