Dado un número entero N , la tarea es imprimir los factores primos de N en orden decreciente utilizando la estructura de datos de la pila.
Ejemplos:
Entrada: N = 34
Salida:
17 2
Explicación:
Los factores primos del número 34 son 2 y 17.Entrada: N = 8
Salida: 2
Enfoque: La idea es usar la estructura de datos Stack para almacenar todos los factores primos de N y, al final, imprimir todos los valores en Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila , digamos st .
- Ejecute un bucle mientras N != 1 . Desde i = 2, para cada valor de i , ejecute un ciclo hasta que N % i == 0 y empuje i en la pila st y actualice N a N/i.
- Finalmente, imprima todos los valores de arriba a abajo de stack st .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print prime factors
// of N in decreasing order
void PrimeFactors(int N)
{
// Stores prime factors of N
// in decreasing order
stack<int> st;
int i = 2;
while (N != 1) {
if (N % i == 0) {
// Insert i into stack
st.push(i);
while (N % i == 0) {
// Update N
N = N / i;
}
}
// Update i
i++;
}
// Print value of stack st
while (!st.empty()) {
printf("%d ", st.top());
st.pop();
}
}
// Driver Code
int main()
{
int N = 8;
// function Call
PrimeFactors(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print prime factors
// of N in decreasing order
static void PrimeFactors(int N)
{
// Stores prime factors of N
// in decreasing order
Stack<Integer> st = new Stack<>();
int i = 2;
while (N != 1)
{
if (N % i == 0)
{
// Insert i into stack
st.push(i);
while (N % i == 0)
{
// Update N
N = N / i;
}
}
// Update i
i++;
}
// Print value of stack st
while (!st.isEmpty())
{
System.out.println(st.peek());
st.pop();
}
}
// Driver Code
public static void main (String[] args)
{
int N = 8;
// Function Call
PrimeFactors(N);;
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to print prime factors # of N in decreasing order def PrimeFactors(N): # Stores prime factors of N # in decreasing order st = [] i = 2 while (N != 1): if (N % i == 0): # Insert i into stack st.append(i) while (N % i == 0): # Update N N = N // i # Update i i += 1 # Print value of stack st while (len(st) != 0): print(st[-1]) st.pop() # Driver Code if __name__ == "__main__": N = 8 # function Call PrimeFactors(N) # This code is contributed by chitranayal.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print prime factors
// of N in decreasing order
static void PrimeFactors(int N)
{
// Stores prime factors of N
// in decreasing order
Stack<int> st = new Stack<int>();
int i = 2;
while (N != 1)
{
if (N % i == 0)
{
// Insert i into stack
st.Push(i);
while (N % i == 0)
{
// Update N
N = N / i;
}
}
// Update i
i++;
}
// Print value of stack st
while (st.Count != 0)
{
Console.Write(st.Peek());
st.Pop();
}
}
// Driver Code
public static void Main ()
{
int N = 8;
// Function Call
PrimeFactors(N);;
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for the above approach
// Function to print prime factors
// of N in decreasing order
function PrimeFactors(N)
{
// Stores prime factors of N
// in decreasing order
let st = [];
let i = 2;
while (N != 1)
{
if (N % i == 0)
{
// Insert i into stack
st.push(i);
while (N % i == 0)
{
// Update N
N = Math.floor(N / i);
}
}
// Update i
i++;
}
// Print value of stack st
while (st.length!=0)
{
document.write(st.pop());
}
}
// Driver Code
let N = 8;
// Function Call
PrimeFactors(N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)