Compruebe si el número es un número de potencia principal

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 2

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *