Dado un número entero N , la tarea es comprobar si el número de divisores de N es primo o no.
Ejemplos:
Entrada: N = 13
Salida: Sí
La cuenta del divisor es 2 (1 y 13), que es primo.Entrada: N = 8
Salida: No
Los divisores son 1, 2, 4 y 8.
Enfoque: Lea este artículo para encontrar el conteo de divisores de un número. Entonces encuentre el valor máximo de i para cada divisor primo p tal que N % (p i ) = 0 . Entonces el conteo de divisores se multiplica por (i + 1) . La cuenta de divisores será (i 1 + 1) * (i 2 + 1) * … * (i k + 1).
Ahora se puede ver que solo puede haber un divisor primo para el máximo i y si N % p i = 0 entonces (i + 1) debería ser primo. La primalidad se puede comprobar en sqrt(n)tiempo y los factores primos también se pueden encontrar en tiempo sqrt(n) . Entonces, la complejidad de tiempo general será O(sqrt(n)) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true
// if n is prime
bool Prime(int n)
{
// There is no prime
// less than 2
if (n < 2)
return false;
// Run a loop from 2 to sqrt(n)
for (int i = 2; i <= sqrt(n); i++)
// If there is any factor
if (n % i == 0)
return false;
return true;
}
// Function that returns true if n
// has a prime count of divisors
bool primeCountDivisors(int n)
{
if (n < 2)
return false;
// Find the prime factors
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0) {
// Find the maximum value of i for every
// prime divisor p such that n % (p^i) == 0
long a = n, c = 0;
while (a % i == 0) {
a /= i;
c++;
}
// If c+1 is a prime number and a = 1
if (a == 1 && Prime(c + 1))
return true;
// The number cannot have two factors
// to have count of divisors prime
else
return false;
}
// Else the number is prime so
// it has only two divisors
return true;
}
// Driver code
int main()
{
int n = 13;
if (primeCountDivisors(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true
// if n is prime
static boolean Prime(int n)
{
// There is no prime
// less than 2
if (n < 2)
return false;
// Run a loop from 2 to sqrt(n)
for (int i = 2; i <= (int)Math.sqrt(n); i++)
// If there is any factor
if (n % i == 0)
return false;
return true;
}
// Function that returns true if n
// has a prime count of divisors
static boolean primeCountDivisors(int n)
{
if (n < 2)
return false;
// Find the prime factors
for (int i = 2; i <= (int)Math.sqrt(n); i++)
if (n % i == 0)
{
// Find the maximum value of i for every
// prime divisor p such that n % (p^i) == 0
long a = n, c = 0;
while (a % i == 0)
{
a /= i;
c++;
}
// If c+1 is a prime number and a = 1
if (a == 1 && Prime((int)c + 1) == true)
return true;
// The number cannot have two factors
// to have count of divisors prime
else
return false;
}
// Else the number is prime so
// it has only two divisors
return true;
}
// Driver code
public static void main (String[] args)
{
int n = 13;
if (primeCountDivisors(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach
from math import sqrt
# Function that returns true
# if n is prime
def Prime(n) :
# There is no prime
# less than 2
if (n < 2) :
return False;
# Run a loop from 2 to sqrt(n)
for i in range(2, int(sqrt(n)) + 1) :
# If there is any factor
if (n % i == 0) :
return False;
return True;
# Function that returns true if n
# has a prime count of divisors
def primeCountDivisors(n) :
if (n < 2) :
return False;
# Find the prime factors
for i in range(2, int(sqrt(n)) + 1) :
if (n % i == 0) :
# Find the maximum value of i for every
# prime divisor p such that n % (p^i) == 0
a = n; c = 0;
while (a % i == 0) :
a //= i;
c += 1;
# If c + 1 is a prime number and a = 1
if (a == 1 and Prime(c + 1)) :
return True;
# The number cannot have two factors
# to have count of divisors prime
else :
return False;
# Else the number is prime so
# it has only two divisors
return True;
# Driver code
if __name__ == "__main__" :
n = 13;
if (primeCountDivisors(n)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true
// if n is prime
static bool Prime(int n)
{
// There is no prime
// less than 2
if (n < 2)
return false;
// Run a loop from 2 to sqrt(n)
for (int i = 2; i <= (int)Math.Sqrt(n); i++)
// If there is any factor
if (n % i == 0)
return false;
return true;
}
// Function that returns true if n
// has a prime count of divisors
static bool primeCountDivisors(int n)
{
if (n < 2)
return false;
// Find the prime factors
for (int i = 2; i <= (int)Math.Sqrt(n); i++)
if (n % i == 0)
{
// Find the maximum value of i for every
// prime divisor p such that n % (p^i) == 0
long a = n, c = 0;
while (a % i == 0)
{
a /= i;
c++;
}
// If c+1 is a prime number and a = 1
if (a == 1 && Prime((int)c + 1) == true)
return true;
// The number cannot have two factors
// to have count of divisors prime
else
return false;
}
// Else the number is prime so
// it has only two divisors
return true;
}
// Driver code
public static void Main()
{
int n = 13;
if (primeCountDivisors(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true
// if n is prime
function Prime(n)
{
// There is no prime
// less than 2
if (n < 2)
return false;
// Run a loop from 2 to sqrt(n)
for(var i = 2; i <= Math.sqrt(n); i++)
// If there is any factor
if (n % i == 0)
return false;
return true;
}
// Function that returns true if n
// has a prime count of divisors
function primeCountDivisors( n)
{
if (n < 2)
return false;
// Find the prime factors
for(var i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
{
// Find the maximum value of i for every
// prime divisor p such that n % (p^i) == 0
var a = n, c = 0;
while (a % i == 0)
{
a /= i;
c++;
}
// If c+1 is a prime number and a = 1
if (a == 1 && Prime(c + 1))
return true;
// The number cannot have two factors
// to have count of divisors prime
else
return false;
}
// Else the number is prime so
// it has only two divisors
return true;
}
// Driver rcode
n = 13;
if (primeCountDivisors(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by SoumikMondal
</script>
Producción:
Yes
Complejidad de tiempo: O (sqrt (n)), ya que estamos usando un ciclo para atravesar sqrt (n) veces. Donde n es el número entero dado como entrada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA