Dado un número entero 
. La tarea es encontrar la superpotencia a partir de la factorización de .
La Superpotencia es la potencia más alta entre las potencias de los números primos en la factorización de un número n.
Ejemplos :
Input : n = 32 Output : 5 Input : n = 240 Output : 4
Para encontrar la superpotencia de cualquier número dado , tenemos que completar la factorización de n y encontrar la potencia más alta entre todos los factores primos.
Nota : El uso de Sieve con el fin de almacenar una lista de números primos es útil en términos de optimización.
Algoritmo :
- Iterar sobre números primos y calcular la factorización de n.
- Para cada número primo entre la lista almacenada de números primos y que también es un factor de n,
encuentra su potencia y comprueba si tiene superpotencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP for finding super power of n
#include <bits/stdc++.h>
#define MAX 100000
using namespace std;
// global hash for prime
bool prime[100002];
// sieve method for storing a list of prime
void SieveOfEratosthenes()
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++)
if (prime[p] == true)
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
// function to return super power
int superpower(int n)
{
SieveOfEratosthenes();
int superPower = 0, factor = 0;
int i = 2;
// find the super power
while (n > 1 && i <= MAX) {
if (prime[i]) {
factor = 0;
while (n % i == 0 && n > 1) {
factor++;
n = n / i;
}
if (superPower < factor)
superPower = factor;
}
i++;
}
return superPower;
}
// Driver program
int main()
{
int n = 256;
cout << superpower(n);
return 0;
}
Java
// Java for finding super power of n
class GFG{
static int MAX=100000;
// global hash for prime
static boolean[] prime=new boolean[100002];
// sieve method for storing a list of prime
static void SieveOfEratosthenes()
{
for (int p = 2; p * p <= MAX; p++)
if (prime[p] == false)
for (int i = p * 2; i <= MAX; i += p)
prime[i] = true;
}
// function to return super power
static int superpower(int n)
{
SieveOfEratosthenes();
int superPower = 0, factor = 0;
int i = 2;
// find the super power
while (n > 1 && i <= MAX) {
if (!prime[i]) {
factor = 0;
while (n % i == 0 && n > 1) {
factor++;
n = n / i;
}
if (superPower < factor)
superPower = factor;
}
i++;
}
return superPower;
}
// Driver program
public static void main(String[] args)
{
int n = 256;
System.out.println(superpower(n));
}
}
// This code is contributed by mits
Python3
# Python3 for finding super # power of n MAX = 100000; # global hash for prime prime = [True] * 100002; # sieve method for storing # a list of prime def SieveOfEratosthenes(): p = 2; while(p * p <= MAX): if (prime[p] == True): i = p * 2; while(i <= MAX): prime[i] = False; i += p; p += 1; # function to return super power def superpower(n): SieveOfEratosthenes(); superPower = 0; factor = 0; i = 2; # find the super power while (n > 1 and i <= MAX): if (prime[i]): factor = 0; while (n % i == 0 and n > 1): factor += 1; n = int(n / i); if (superPower < factor): superPower = factor; i += 1; return superPower; # Driver Code n = 256; print(superpower(n)); # This code is contributed by mits
C#
// C# for finding super power of n
class GFG
{
static int MAX = 100000;
// global hash for prime
static bool[] prime = new bool[100002];
// sieve method for storing
// a list of prime
static void SieveOfEratosthenes()
{
for (int p = 2;
p * p <= MAX; p++)
if (prime[p] == false)
for (int i = p * 2;
i <= MAX; i += p)
prime[i] = true;
}
// function to return super power
static int superpower(int n)
{
SieveOfEratosthenes();
int superPower = 0, factor = 0;
int i = 2;
// find the super power
while (n > 1 && i <= MAX)
{
if (!prime[i])
{
factor = 0;
while (n % i == 0 && n > 1)
{
factor++;
n = n / i;
}
if (superPower < factor)
superPower = factor;
}
i++;
}
return superPower;
}
// Driver Code
static void Main()
{
int n = 256;
System.Console.WriteLine(superpower(n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP for finding super power of n
$MAX = 100000;
// global hash for prime
$prime = array_fill(0, 100002, true);
// sieve method for storing
// a list of prime
function SieveOfEratosthenes()
{
global $MAX, $prime;
for ($p = 2; $p * $p <= $MAX; $p++)
if ($prime[$p] == true)
for ($i = $p * 2;
$i <= $MAX; $i += $p)
$prime[$i] = false;
}
// function to return super power
function superpower($n)
{
SieveOfEratosthenes();
global $MAX, $prime;
$superPower = 0;
$factor = 0;
$i = 2;
// find the super power
while ($n > 1 && $i <= $MAX)
{
if ($prime[$i])
{
$factor = 0;
while ($n % $i == 0 && $n > 1)
{
$factor++;
$n = $n / $i;
}
if ($superPower < $factor)
$superPower = $factor;
}
$i++;
}
return $superPower;
}
// Driver Code
$n = 256;
echo superpower($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript for finding super power of n
var MAX = 100000;
// global hash for prime
var prime = Array(100002).fill(true);
// sieve method for storing a list of prime
function SieveOfEratosthenes()
{
for (var p = 2; p * p <= MAX; p++)
if (prime[p] == true)
for (var i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
// function to return super power
function superpower(n)
{
SieveOfEratosthenes();
var superPower = 0, factor = 0;
var i = 2;
// find the super power
while (n > 1 && i <= MAX) {
if (prime[i]) {
factor = 0;
while (n % i == 0 && n > 1) {
factor++;
n = n / i;
}
if (superPower < factor)
superPower = factor;
}
i++;
}
return superPower;
}
// Driver program
var n = 256;
document.write( superpower(n));
</script>
Producción:
8
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA