Un número n se dice Número Poderoso si por cada factor primo p de él, p 2 también lo divide. Por ejemplo: – 36 es un número poderoso. Es divisible tanto por 3 como por el cuadrado de 3, es decir, 9.
Los primeros Números Poderosos son:
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64….
Dado un número n, nuestra tarea es verificar si este es poderoso o no.
Ejemplos:
Input: 27 Output: YES Input: 32 Output: YES Input: 12 Output: NO
La idea se basa en el hecho de que si un número n es poderoso, entonces todos sus factores primos y sus cuadrados deben ser divisibles por n. Encontramos todos los factores primos de un número dado . Y para cada factor primo, encontramos la potencia más alta que divide a n. Si encontramos un factor primo cuyo mayor poder divisor es 1, devolvemos falso. Si el poder de división más alto de todos los factores primos es mayor que 1, devolvemos verdadero.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find if a number is powerful or not.
#include <bits/stdc++.h>
using namespace std;
// function to check if the number is powerful
bool isPowerful(int n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// If only 2^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// if n is not a power of 2 then this loop will execute
// repeat above process
for (int factor = 3; factor <= sqrt(n); factor += 2) {
// Find highest power of "factor" that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// If only factor^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not a prime numenr.
// Since prime numbers are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Driver program to test above function
int main()
{
isPowerful(20) ? cout << "YES\n" : cout << "NO\n";
isPowerful(27) ? cout << "YES\n" : cout << "NO\n";
return 0;
}
Java
// Java program to find if a
// number is powerful or not.
class GFG {
// function to check if the
// number is powerful
static boolean isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// If only 2^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// if n is not a power of 2 then this loop will execute
// repeat above process
for (int factor = 3; factor <= Math.sqrt(n); factor += 2) {
// Find highest power of "factor" that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// If only factor^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not a prime numenr.
// Since prime numbers are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Driver code
public static void main(String[] args)
{
if (isPowerful(20))
System.out.print("YES\n");
else
System.out.print("NO\n");
if (isPowerful(27))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find
# if a number is powerful or not.
import math
# function to check if
# the number is powerful
def isPowerful(n):
# First divide the number repeatedly by 2
while (n % 2 == 0):
power = 0
while (n % 2 == 0):
n = n//2
power = power + 1
# If only 2 ^ 1 divides
# n (not higher powers),
# then return false
if (power == 1):
return False
# if n is not a power of 2
# then this loop will execute
# repeat above process
for factor in range(3, int(math.sqrt(n))+1, 2):
# Find highest power of
# "factor" that divides n
power = 0
while (n % factor == 0):
n = n//factor
power = power + 1
# If only factor ^ 1 divides
# n (not higher powers),
# then return false
if (power == 1):
return false
# n must be 1 now if it
# is not a prime number.
# Since prime numbers are
# not powerful, we return
# false if n is not 1.
return (n == 1)
# Driver code
print("YES" if isPowerful(20) else "NO")
print("YES" if isPowerful(27) else "NO")
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find if a
// number is powerful or not.
using System;
class GFG {
// function to check if the
// number is powerful
static bool isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// If only 2^1 divides n
// (not higher powers),
// then return false
if (power == 1)
return false;
}
// if n is not a power of 2 then
// this loop will execute repeat
// above process
for (int factor = 3; factor <= Math.Sqrt(n); factor += 2) {
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// If only factor^1 divides n
// (not higher powers), then
// return false
if (power == 1)
return false;
}
// n must be 1 now if it is not
// a prime numenr.
// Since prime numbers are not
// powerful, we return false if
// n is not 1.
return (n == 1);
}
// Driver code
public static void Main()
{
if (isPowerful(20))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
if (isPowerful(27))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find if a
// number is powerful or not
// function to check if
// the number is powerful
function isPowerful($n)
{
// First divide the
// number repeatedly by 2
while ($n % 2 == 0)
{
$power = 0;
while ($n % 2 == 0)
{
$n /= 2;
$power++;
}
// If only 2^1 divides
// n (not higher powers),
// then return false
if ($power == 1)
return false;
}
// if n is not a power of 2
// then this loop will execute
// repeat above process
for ($factor = 3;
$factor <= sqrt($n);
$factor += 2)
{
// Find highest power of
// "factor" that divides n
$power = 0;
while ($n % $factor == 0)
{
$n = $n / $factor;
$power++;
}
// If only factor^1 divides
// n (not higher powers),
// then return false
if ($power == 1)
return false;
}
// n must be 1 now if it is
// not a prime number. Since
// prime numbers are not powerful,
// we return false if n is not 1.
return ($n == 1);
}
// Driver Code
$d = isPowerful(20) ?
"YES\n" :
"NO\n";
echo $d;
$d = isPowerful(27) ?
"YES\n" :
"NO\n";
echo $d;
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find if a
// number is powerful or not.
// function to check if the
// number is powerful
function isPowerful(n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0) {
let power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// If only 2^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// if n is not a power of 2 then this loop will execute
// repeat above process
for (let factor = 3; factor <= Math.sqrt(n); factor += 2) {
// Find highest power of "factor" that divides n
let power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// If only factor^1 divides n (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not a prime numenr.
// Since prime numbers are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Driver code to test above methods
if (isPowerful(20))
document.write("YES" + "<br>");
else
document.write("NO" + "<br>");
if (isPowerful(27))
document.write("YES" + "<br>");
else
document.write("NO" + "<br>");
// This code is contributed by avijitmondal1998.
</script>
Producción :
NO YES
Referencias:
https://en.wikipedia.org/wiki/Powerful_number
Este artículo es una contribución de Harsh Agarwal . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA