Dado un número entero N , la tarea es verificar si el número es un número de potencia primo. En caso afirmativo, imprima el número junto con su potencia, que es igual a N. De lo contrario, imprima -1.
Una potencia prima es una potencia entera positiva de un solo número primo.
Por ejemplo: 7 = 7 1 , 9 = 3 2 y 32 = 2 5 son potencias primas, mientras que 6 = 2 × 3, 12 = 22 × 3 y 36 = 62 = 22 × 32 no lo son. (El número 1 no se cuenta como potencia principal).
Nota: Si no existe tal número primo, imprima -1.
Ejemplos:
Entrada: N = 49
Salida: 7 2
Explicación:
N se puede representar como una potencia del número primo 7.
N = 49 = 7 2Entrada: N = 100
Salida: -1
Explicación:
N no se puede representar como una potencia de ningún número primo.
Planteamiento: La idea es usar la Criba de Eratóstenes para encontrar todos los números primos. Luego, itere sobre todos los números primos y verifique que si algún número primo divide el número dado N, si es así, divídalo hasta que se convierta en 1 o no sea divisible por ese número primo. Finalmente, verifique que el número sea igual a 1. Si es así, devuelva el número primo; de lo contrario, el número dado no se puede expresar como un número primo elevado a alguna potencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to check if
// a number is a prime power number
#include<bits/stdc++.h>
using namespace std;
// Array to store the
// prime numbers
bool is_prime[1000001];
vector<int> primes;
// Function to mark the prime
// numbers using Sieve of
// Eratosthenes
void SieveOfEratosthenes(int n)
{
int p = 2;
for(int i = 0; i < n; i++)
is_prime[i] = true;
while (p * p <= n)
{
// If prime[p] is not
// changed, then it is a prime
if (is_prime[p] == true)
{
// Update all multiples of p
for(int i = p * p; i < n + 1; i += p)
{
is_prime[i] = false;
}
}
p += 1;
}
for(int i = 2; i < n + 1; i++)
{
if (is_prime[i])
primes.push_back(i);
}
}
// Function to check if the
// number can be represented
// as a power of prime
pair<int, int> power_of_prime(int n)
{
for(auto i : primes)
{
if (n % i == 0)
{
int c = 0;
while(n % i == 0)
{
n /= i;
c += 1;
}
if(n == 1)
return {i, c};
else
return {-1, 1};
}
}
}
// Driver Code
int main()
{
int n = 49;
SieveOfEratosthenes(int(sqrt(n)) + 1);
// Function Call
pair<int, int> p = power_of_prime(n);
if (p.first > 1)
cout << p.first << " ^ "
<< p.second << endl;
else
cout << -1 << endl;
}
// This code is contributed by Surendra_Gangwar
Java
// Java implementation to check if
// a number is a prime power number
import java.io.*;
import java.util.*;
import java.lang.Math;
class GFG{
// Array to store the
// prime numbers
static ArrayList<Integer> primes = new ArrayList<Integer>();
// Function to mark the prime
// numbers using Sieve of
// Eratosthenes
public static void sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
boolean prime[] = new boolean[n + 1];
for(int i = 0; i < n; i++)
prime[i] = true;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if(prime[p] == true)
{
// Update all multiples of p
for(int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for(int i = 2; i <= n; i++)
{
if(prime[i] == true)
primes.add(i);
}
}
// Function to check if the
// number can be represented
// as a power of prime
public static int[] power_of_prime(int n)
{
for(int ii = 0; ii < primes.size(); ii++)
{
int i = primes.get(ii);
if (n % i == 0)
{
int c = 0;
while(n % i == 0)
{
n /= i;
c += 1;
}
if(n == 1)
return new int[]{i, c};
else
return new int[]{-1, 1};
}
}
return new int[]{-1, 1};
}
// Driver code
public static void main(String args[])
{
int n = 49;
int sq = (int)(Math.sqrt(n));
sieveOfEratosthenes(sq + 1);
// Function call
int arr[] = power_of_prime(n);
if (arr[0] > 1)
System.out.println(arr[0] + " ^ " + arr[1]);
else
System.out.println("-1");
}
}
// This code is contributed by grand_master
Python3
# Python3 implementation to check # if a number is a prime power number from math import * # Array to store the # prime numbers is_prime = [True for i in range(10**6 + 1)] primes =[] # Function to mark the prime # numbers using Sieve of # Eratosthenes def SieveOfEratosthenes(n): p = 2 while (p * p <= n): # If prime[p] is not # changed, then it is a prime if (is_prime[p] == True): # Update all multiples of p for i in range(p * p, n + 1, p): is_prime[i] = False p += 1 for i in range(2, n + 1): if is_prime[i]: primes.append(i) # Function to check if the # number can be represented # as a power of prime def power_of_prime(n): for i in primes: if n % i == 0: c = 0 while n % i == 0: n//= i c += 1 if n == 1: return (i, c) else: return (-1, 1) # Driver Code if __name__ == "__main__": n = 49 SieveOfEratosthenes(int(sqrt(n))+1) # Function Call num, power = power_of_prime(n) if num > 1: print(num, "^", power) else: print(-1)
C#
// C# implementation to check if
// a number is a prime power number
using System;
using System.Collections;
class GFG{
// Array to store the
// prime numbers
static ArrayList primes = new ArrayList();
// Function to mark the prime
// numbers using Sieve of
// Eratosthenes
public static void sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
bool []prime = new bool[n + 1];
for(int i = 0; i < n; i++)
prime[i] = true;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for(int i = 2; i <= n; i++)
{
if (prime[i] == true)
primes.Add(i);
}
}
// Function to check if the
// number can be represented
// as a power of prime
public static int[] power_of_prime(int n)
{
for(int ii = 0; ii < primes.Count; ii++)
{
int i = (int)primes[ii];
if (n % i == 0)
{
int c = 0;
while (n % i == 0)
{
n /= i;
c += 1;
}
if (n == 1)
return new int[]{i, c};
else
return new int[]{-1, 1};
}
}
return new int[]{-1, 1};
}
// Driver code
public static void Main(string []args)
{
int n = 49;
int sq = (int)(Math.Sqrt(n));
sieveOfEratosthenes(sq + 1);
// Function call
int []arr = power_of_prime(n);
if (arr[0] > 1)
Console.Write(arr[0] + " ^ " +
arr[1]);
else
Console.Write("-1");
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to check if
// a number is a prime power number
// Array to store the
// prime numbers
let primes = [];
// Function to mark the prime
// numbers using Sieve of
// Eratosthenes
function sieveOfEratosthenes(n)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
let prime = Array.from({length: n+1}, (_, i) => 0);
for(let i = 0; i < n; i++)
prime[i] = true;
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(let i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for(let i = 2; i <= n; i++)
{
if (prime[i] == true)
primes.push(i);
}
}
// Function to check if the
// number can be represented
// as a power of prime
function power_of_prime(n)
{
for(let ii = 0; ii < primes.length; ii++)
{
let i = primes[ii];
if (n % i == 0)
{
let c = 0;
while (n % i == 0)
{
n /= i;
c += 1;
}
if (n == 1)
return [i, c];
else
return [-1, 1];
}
}
return [-1, 1];
}
// Driver Code
let n = 49;
let sq = (Math.sqrt(n));
sieveOfEratosthenes(sq + 1);
// Function call
let arr = power_of_prime(n);
if (arr[0] > 1)
document.write(arr[0] + " ^ " +
arr[1]);
else
document.write("-1");
</script>
Producción:
7 ^ 2
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA