Comprobar si un número tiene exactamente tres factores distintos o no

Dado un entero positivo n(1 <= n <= 10 ¹⁸ ). Comprueba si un número tiene exactamente tres factores distintos o no. Escriba “ Sí ” si tiene de otra manera “ No ”.

Ejemplos: 

Input : 9
Output: Yes
Explanation
Number 9 has exactly three factors:
1, 3, 9, hence answer is 'Yes'

Input  : 10
Output : No

El enfoque simple es contar factores generando todos los divisores de un número usando este enfoque, luego verifique si el conteo de todos los factores es igual a ‘3’ o no. La complejidad temporal de este enfoque es O(sqrt(n)). 

Un mejor enfoque es utilizar la teoría de números . De acuerdo con la propiedad del cuadrado perfecto, » Todo cuadrado perfecto (x ² ) siempre tiene solo números impares de factores «. 

Si la raíz cuadrada de un número dado (digamos x ² ) es primo (después de confirmar que el número es un cuadrado perfecto), entonces debe tener exactamente tres factores distintos, es decir, 

1. Un número 1 por supuesto.
2. Raíz cuadrada de un número, es decir, x (número primo).
3. Número en sí mismo, es decir, x ² .

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

// C++ program to check whether number
// has exactly three distinct factors
// or not
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to check whether a
// number is prime or not
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to check whether given number
// has three distinct factors or not
bool isThreeDisctFactors(long long n)
{
    // Find square root of number
    int sq = (int)sqrt(n);
 
    // Check whether number is perfect
    // square or not
    if (1LL * sq * sq != n)
        return false;
 
    // If number is perfect square, check
    // whether square root is prime or
    // not
    return isPrime(sq) ? true : false;
}
 
// Driver program
int main()
{
    long long num = 9;
    if (isThreeDisctFactors(num))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    num = 15;
    if (isThreeDisctFactors(num))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    num = 12397923568441;
    if (isThreeDisctFactors(num))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    return 0;
}

// Java program to check whether number
// has exactly three distinct factors
// or not
public class GFG {
 
 
// Utility function to check whether a
// number is prime or not
static boolean isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to check whether given number
// has three distinct factors or not
static boolean isThreeDisctFactors(long n)
{
    // Find square root of number
    int sq = (int)Math.sqrt(n);
 
    // Check whether number is perfect
    // square or not
    if (1L * sq * sq != n)
        return false;
 
    // If number is perfect square, check
    // whether square root is prime or
    // not
    return isPrime(sq) ? true : false;
}
 
// Driver program
    public static void main(String[] args) {
        long num = 9;
    if (isThreeDisctFactors(num))
        System.out.println("Yes");
    else
        System.out.println("No");
 
    num = 15;
    if (isThreeDisctFactors(num))
        System.out.println("Yes");
    else
        System.out.println("No");
 
    num = 12397923568441L;
    if (isThreeDisctFactors(num))
        System.out.println("Yes");
    else
        System.out.println("No");
    }
}

# Python 3 program to check whether number
# has exactly three distinct factors
# or not
 
from math import sqrt
# Utility function to check whether a
# number is prime or not
def isPrime(n):
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False
     
    k= int(sqrt(n))+1
    for i in range(5,k,6):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
 
    return True
 
# Function to check whether given number
# has three distinct factors or not
def isThreeDisctFactors(n):
    # Find square root of number
    sq = int(sqrt(n))
 
    # Check whether number is perfect
    # square or not
    if (1 * sq * sq != n):
        return False
 
    # If number is perfect square, check
    # whether square root is prime or
    # not
    if (isPrime(sq)):
        return True
    else:
        return False
 
# Driver program
if __name__ == '__main__':
    num = 9
    if (isThreeDisctFactors(num)):
        print("Yes")
    else:
        print("No")
 
    num = 15
    if (isThreeDisctFactors(num)):
        print("Yes")
    else:
        print("No")
 
    num = 12397923568441
    if (isThreeDisctFactors(num)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surendra_Gangwar

// C# program to check whether number
// has exactly three distinct factors
// or not
using System;
 
public class GFG {
 
    // Utility function to check whether
    // a number is prime or not
    static bool isPrime(int n)
    {
 
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can
        // skip middle five numbers in
        // below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to check whether given number
    // has three distinct factors or not
    static bool isThreeDisctFactors(long n)
    {
 
        // Find square root of number
        int sq = (int)Math.Sqrt(n);
 
        // Check whether number is perfect
        // square or not
        if (1LL * sq * sq != n)
            return false;
 
        // If number is perfect square, check
        // whether square root is prime or
        // not
        return isPrime(sq) ? true : false;
    }
 
    // Driver program
    static public void Main()
    {
        long num = 9;
        if (isThreeDisctFactors(num))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
 
        num = 15;
        if (isThreeDisctFactors(num))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
 
        num = 12397923568441;
        if (isThreeDisctFactors(num))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This Code is contributed by vt_m.

<?php
// PHP program to check whether
// number has exactly three
// distinct factors or not
 
// Utility function to check
// whether a number is prime
// or not
function isPrime($n)
{
    // Corner cases
    if ($n <= 1)
        return false;
    if ($n <= 3)
        return true;
 
    // This is checked so that
    // we can skip middle five
    // numbers in below loop
    if ($n % 2 == 0 || $n % 3 == 0)
        return false;
 
    for ($i = 5; $i * $i <= $n;
                   $i = $i + 6)
        if ($n % $i == 0 ||
            $n % ($i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to check
// whether given number
// has three distinct
// factors or not
function isThreeDisctFactors($n)
{
    // Find square root of number
    $sq = sqrt($n);
 
    // Check whether number is
    // perfect square or not
    if ($sq * $sq != $n)
        return false;
 
    // If number is perfect square,
    // check whether square root is
    // prime or not
    return isPrime($sq) ? true : false;
}
 
// Driver Code
$num = 9;
if (isThreeDisctFactors($num))
    echo "Yes\n";
else
    echo "No\n";
 
$num = 15;
if (isThreeDisctFactors($num))
    echo "Yes\n";
else
    echo "No\n";
 
$num = 12397923568441;
if (isThreeDisctFactors($num))
    echo "Yes\n";
else
    echo "No\n";
 
// This code is contributed by ak_t
?>

<script>
 
// Javascript program to check whether
// number has exactly three distinct
// factors or not
 
// Utility function to check whether a
// number is prime or not
function isPrime(n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for(let i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to check whether given number
// has three distinct factors or not
function isThreeDisctFactors(n)
{
     
    // Find square root of number
    let sq = parseInt(Math.sqrt(n));
 
    // Check whether number is perfect
    // square or not
    if (sq * sq != n)
        return false;
 
    // If number is perfect square, check
    // whether square root is prime or
    // not
    return isPrime(sq) ? true : false;
}
 
// Driver code
let num = 9;
if (isThreeDisctFactors(num))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
num = 15;
if (isThreeDisctFactors(num))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
num = 12397923568441;
if (isThreeDisctFactors(num))
    document.write("Yes<br>");
else
    document.write("No<br>");
     
// This code is contributed by souravmahato348 
 
</script>

Producción : 

Yes
No
No

Complejidad temporal : O(n ^1/4 ) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.-