Imprime todos los factores primos y sus potencias

Dado un número N, imprime todos sus factores primos únicos y sus potencias en N. 
Ejemplos: 
 

Input: N = 100
Output: Factor Power
          2      2
          5      2

Input: N = 35
Output: Factor  Power
          5      1
          7      1

Una solución simple es encontrar primero los factores primos de N. Luego, para cada factor primo, encuentre la potencia más alta que divide a N e imprímala.
Una Solución Eficiente es usar Tamiz de Eratóstenes
 

1) First compute an array s[N+1] using Sieve of Eratosthenes.

s[i] = Smallest prime factor of "i" that
       divides "i".

For example let N  = 10
  s[2] = s[4] = s[6] = s[8] = s[10] = 2;
  s[3] = s[9] = 3;
  s[5] = 5;
  s[7] = 7;


2) Using the above computed array s[],
   we can find all powers in O(Log N) time.

    curr = s[N];  // Current prime factor of N
    cnt = 1;   // Power of current prime factor

    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];

        // N is now N/s[N].  If new N also has its 
        // smallest prime factor as curr, increment 
        // power and continue
        if (curr == s[N])
        {
            cnt++;
            continue;
        }

        // Print prime factor and its power
        print(curr, cnt);

        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }

A continuación se muestra la implementación de los pasos anteriores.
 

C++

// C++ Program to print prime factors and their
// powers using Sieve Of Eratosthenes
#include<bits/stdc++.h>
using namespace std;
 
// Using SieveOfEratosthenes to find smallest prime
// factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
void sieveOfEratosthenes(int N, int s[])
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries in it as false.
    vector <bool> prime(N+1, false);
 
    // Initializing smallest factor equal to 2
    // for all the even numbers
    for (int i=2; i<=N; i+=2)
        s[i] = 2;
 
    // For odd numbers less than equal to n
    for (int i=3; i<=N; i+=2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is the number itself
            s[i] = i;
 
            // For all multiples of current prime number
            for (int j=i; j*i<=N; j+=2)
            {
                if (prime[i*j] == false)
                {
                    prime[i*j] = true;
 
                    // i is the smallest prime factor for
                    // number "i*j".
                    s[i*j] = i;
                }
            }
        }
    }
}
 
// Function to generate prime factors and its power
void generatePrimeFactors(int N)
{
    // s[i] is going to store smallest prime factor
    // of i.
    int s[N+1];
 
    // Filling values in s[] using sieve
    sieveOfEratosthenes(N, s);
 
    printf("Factor Power\n");
 
    int curr = s[N];  // Current prime factor of N
    int cnt = 1;   // Power of current prime factor
 
    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];
 
        // N is now N/s[N].  If new N als has smallest
        // prime factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }
 
        printf("%d\t%d\n", curr, cnt);
 
        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }
}
 
//Driver Program
int main()
{
    int N = 360;
    generatePrimeFactors(N);
    return 0;
}

Java

// Java Program to print prime
// factors and their powers using
// Sieve Of Eratosthenes
class GFG
{
// Using SieveOfEratosthenes
// to find smallest prime
// factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
static void sieveOfEratosthenes(int N,
                                int s[])
{
    // Create a boolean array
    // "prime[0..n]"  and initialize
    // all entries in it as false.
    boolean[] prime = new boolean[N + 1];
 
    // Initializing smallest
    // factor equal to 2
    // for all the even numbers
    for (int i = 2; i <= N; i += 2)
        s[i] = 2;
 
    // For odd numbers less
    // then equal to n
    for (int i = 3; i <= N; i += 2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is
            // the number itself
            s[i] = i;
 
            // For all multiples of
            // current prime number
            for (int j = i; j * i <= N; j += 2)
            {
                if (prime[i * j] == false)
                {
                    prime[i * j] = true;
 
                    // i is the smallest prime
                    // factor for number "i*j".
                    s[i * j] = i;
                }
            }
        }
    }
}
 
// Function to generate prime
// factors and its power
static void generatePrimeFactors(int N)
{
    // s[i] is going to store
    // smallest prime factor of i.
    int[] s = new int[N + 1];
 
    // Filling values in s[] using sieve
    sieveOfEratosthenes(N, s);
 
    System.out.println("Factor Power");
 
    int curr = s[N]; // Current prime factor of N
    int cnt = 1; // Power of current prime factor
 
    // Printing prime factors
    // and their powers
    while (N > 1)
    {
        N /= s[N];
 
        // N is now N/s[N]. If new N
        // also has smallest prime
        // factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }
 
        System.out.println(curr + "\t" + cnt);
 
        // Update current prime factor
        // as s[N] and initializing
        // count as 1.
        curr = s[N];
        cnt = 1;
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 360;
    generatePrimeFactors(N);
}
}
 
// This code is contributed by mits

Python3

# Python3 program to print prime
# factors and their powers
# using Sieve Of Eratosthenes
 
# Using SieveOfEratosthenes to
# find smallest prime factor
# of all the numbers.
 
# For example, if N is 10,
# s[2] = s[4] = s[6] = s[10] = 2
# s[3] = s[9] = 3
# s[5] = 5
# s[7] = 7
def sieveOfEratosthenes(N, s):
     
    # Create a boolean array
    # "prime[0..n]" and initialize
    # all entries in it as false.
    prime = [False] * (N+1)
 
    # Initializing smallest factor
    # equal to 2 for all the even
    # numbers
    for i in range(2, N+1, 2):
        s[i] = 2
 
    # For odd numbers less than
    # equal to n
    for i in range(3, N+1, 2):
        if (prime[i] == False):
             
            # s(i) for a prime is
            # the number itself
            s[i] = i
 
            # For all multiples of
            # current prime number
            for j in range(i, int(N / i) + 1, 2):
                if (prime[i*j] == False):
                    prime[i*j] = True
 
                    # i is the smallest
                    # prime factor for
                    # number "i*j".
                    s[i * j] = i
 
# Function to generate prime
# factors and its power
def generatePrimeFactors(N):
 
    # s[i] is going to store
    # smallest prime factor
    # of i.
    s = [0] * (N+1)
 
    # Filling values in s[]
    # using sieve
    sieveOfEratosthenes(N, s)
 
    print("Factor Power")
 
    # Current prime factor of N
    curr = s[N]
     
    # Power of current prime factor
    cnt = 1
 
    # Printing prime factors and
    #their powers
    while (N > 1):
        N //= s[N]
 
        # N is now N/s[N]. If new N
        # also has smallest prime
        # factor as curr, increment
        # power
        if (curr == s[N]):
            cnt += 1
            continue
 
        print(str(curr) + "\t" + str(cnt))
 
        # Update current prime factor
        # as s[N] and initializing
        # count as 1.
        curr = s[N]
        cnt = 1
 
#Driver Program
N = 360
generatePrimeFactors(N)
 
# This code is contributed by Ansu Kumari

C#

// C# Program to print prime
// factors and their powers using
// Sieve Of Eratosthenes
class GFG
{
// Using SieveOfEratosthenes
// to find smallest prime
// factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
static void sieveOfEratosthenes(int N, int[] s)
{
    // Create a boolean array
    // "prime[0..n]" and initialize
    // all entries in it as false.
    bool[] prime = new bool[N + 1];
 
    // Initializing smallest
    // factor equal to 2
    // for all the even numbers
    for (int i = 2; i <= N; i += 2)
        s[i] = 2;
 
    // For odd numbers less
    // then equal to n
    for (int i = 3; i <= N; i += 2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is
            // the number itself
            s[i] = i;
 
            // For all multiples of
            // current prime number
            for (int j = i; j * i <= N; j += 2)
            {
                if (prime[i * j] == false)
                {
                    prime[i * j] = true;
 
                    // i is the smallest prime
                    // factor for number "i*j".
                    s[i * j] = i;
                }
            }
        }
    }
}
 
// Function to generate prime
// factors and its power
static void generatePrimeFactors(int N)
{
    // s[i] is going to store
    // smallest prime factor of i.
    int[] s = new int[N + 1];
 
    // Filling values in s[] using sieve
    sieveOfEratosthenes(N, s);
 
    System.Console.WriteLine("Factor Power");
 
    int curr = s[N]; // Current prime factor of N
    int cnt = 1; // Power of current prime factor
 
    // Printing prime factors
    // and their powers
    while (N > 1)
    {
        N /= s[N];
 
        // N is now N/s[N]. If new N
        // also has smallest prime
        // factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }
 
        System.Console.WriteLine(curr + "\t" + cnt);
 
        // Update current prime factor
        // as s[N] and initializing
        // count as 1.
        curr = s[N];
        cnt = 1;
    }
}
 
// Driver Code
static void Main()
{
    int N = 360;
    generatePrimeFactors(N);
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP Program to print prime factors and
// their powers using Sieve Of Eratosthenes
 
// Using SieveOfEratosthenes to find smallest
// prime factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
function sieveOfEratosthenes($N, &$s)
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries in it as false.
    $prime = array_fill(0, $N + 1, false);
 
    // Initializing smallest factor equal
    // to 2 for all the even numbers
    for ($i = 2; $i <= $N; $i += 2)
        $s[$i] = 2;
 
    // For odd numbers less than equal to n
    for ($i = 3; $i <= $N; $i += 2)
    {
        if ($prime[$i] == false)
        {
            // s(i) for a prime is the
            // number itself
            $s[$i] = $i;
 
            // For all multiples of current
            // prime number
            for ($j = $i; $j * $i <= $N; $j += 2)
            {
                if ($prime[$i * $j] == false)
                {
                    $prime[$i * $j] = true;
 
                    // i is the smallest prime factor
                    // for number "i*j".
                    $s[$i * $j] = $i;
                }
            }
        }
    }
}
 
// Function to generate prime factors
// and its power
function generatePrimeFactors($N)
{
    // s[i] is going to store smallest
    // prime factor of i.
    $s = array_fill(0, $N + 1, 0);
 
    // Filling values in s[] using sieve
    sieveOfEratosthenes($N, $s);
 
    print("Factor Power\n");
 
    $curr = $s[$N]; // Current prime factor of N
    $cnt = 1; // Power of current prime factor
 
    // Printing prime factors and their powers
    while ($N > 1)
    {
        if($s[$N])
        $N = (int)($N / $s[$N]);
 
        // N is now N/s[N]. If new N als has smallest
        // prime factor as curr, increment power
        if ($curr == $s[$N])
        {
            $cnt++;
            continue;
        }
 
        print($curr . "\t" . $cnt . "\n");
 
        // Update current prime factor as s[N]
        // and initializing count as 1.
        $curr = $s[$N];
        $cnt = 1;
    }
}
 
// Driver Code
$N = 360;
generatePrimeFactors($N);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// javascript Program to print prime
// factors and their powers using
// Sieve Of Eratosthenes
 
// Using SieveOfEratosthenes
// to find smallest prime
// factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
function sieveOfEratosthenes(N,  s)
{
    // Create a boolean array
    // "prime[0..n]"  and initialize
    // all entries in it as false.
    prime = Array.from({length: N+1}, (_, i) => false);
 
    // Initializing smallest
    // factor equal to 2
    // for all the even numbers
    for (i = 2; i <= N; i += 2)
        s[i] = 2;
 
    // For odd numbers less
    // then equal to n
    for (i = 3; i <= N; i += 2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is
            // the number itself
            s[i] = i;
 
            // For all multiples of
            // current prime number
            for (j = i; j * i <= N; j += 2)
            {
                if (prime[i * j] == false)
                {
                    prime[i * j] = true;
 
                    // i is the smallest prime
                    // factor for number "i*j".
                    s[i * j] = i;
                }
            }
        }
    }
}
 
// Function to generate prime
// factors and its power
function generatePrimeFactors(N)
{
    // s[i] is going to store
    // smallest prime factor of i.
    var s = Array.from({length: N+1}, (_, i) => 0);
 
    // Filling values in s using sieve
    sieveOfEratosthenes(N, s);
 
    document.write("Factor Power");
 
    var curr = s[N]; // Current prime factor of N
    var cnt = 1; // Power of current prime factor
 
    // Printing prime factors
    // and their powers
    while (N > 1)
    {
        N /= s[N];
 
        // N is now N/s[N]. If new N
        // also has smallest prime
        // factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }
 
        document.write("<br>"+curr + "\t" + cnt);
 
        // Update current prime factor
        // as s[N] and initializing
        // count as 1.
        curr = s[N];
        cnt = 1;
    }
}
 
// Driver Code
var N = 360;
generatePrimeFactors(N);
 
 
// This code contributed by Princi Singh
</script>

Producción: 
 

Factor  Power
  2      3
  3      2
  5      1

El algoritmo anterior encuentra todas las potencias en el tiempo O(Log N) después de haber llenado s[]. Esto puede ser muy útil en un entorno competitivo donde tenemos un límite superior y necesitamos calcular factores primos y sus potencias para muchos casos de prueba. En este escenario, la array debe llenarse s[] solo una vez.
Este artículo es una contribución de Rahul Agrawal . 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

Deja una respuesta

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