Dado un número K , la tarea es imprimir los números primos presentes en ese nivel dado que todos los números primos están representados en forma de árbol binario .
Ejemplos:
Input: K = 3
2
/ \
3 5
/\ / \
7 11 13 17
Output :7, 11, 13, 17
Explanation:
2
/ \
3 5
/\ / \
7 11 13 17
So primes present at level 3 : 7, 11, 13, 17
Input :K = 2
2
/ \
3 5
Output :3 5
Enfoque ingenuo: el enfoque ingenuo es construir un árbol binario de números primos y luego obtener elementos en un nivel particular k.
No funciona bien para números grandes, ya que lleva demasiado tiempo.
Enfoque eficiente: Supongamos que hay n elementos y la tarea es construir un árbol binario usando esos n elementos, luego se pueden construir usando log 2 n niveles.
Por lo tanto, dado un nivel k, los elementos presentes aquí son de 2 k-1 a 2 k – 1 si todos los números primos están presentes en una array 1D.
Por lo tanto, el siguiente es el algoritmo:
- Encuentra los números primos hasta MAX_SIZE usando Sieve of Eratosthenes.
- Calcule el índice izquierdo y el índice derecho del nivel como índice izquierdo = 2 k-1 , índice derecho = 2 k -1.
- Da salida a números primos desde el índice izquierdo al índice derecho de la array de números primos.
C++
// CPP program of the approach
#include <bits/stdc++.h>
using namespace std;
// initializing the max value
#define MAX_SIZE 1000005
// To store all prime numbers
vector<int> primes;
// Function to generate N prime numbers using
// Sieve of Eratosthenes
void SieveOfEratosthenes(vector<int>& primes)
{
// Create a boolean array "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true. A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
bool IsPrime[MAX_SIZE];
memset(IsPrime, true, sizeof(IsPrime));
for (int p = 2; p * p < MAX_SIZE; p++) {
// If IsPrime[p] is not changed, then it is a prime
if (IsPrime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.push_back(p);
}
void printLevel(int level)
{
cout << "primes at level " << level << ": ";
int left_index = pow(2, level - 1);
int right_index = pow(2, level) - 1;
for (int i = left_index; i <= right_index; i++) {
cout << primes[i - 1] << " ";
}
cout << endl;
}
// Driver Code
int main()
{
// Function call
SieveOfEratosthenes(primes);
printLevel(1);
printLevel(2);
printLevel(3);
printLevel(4);
return 0;
}
Java
// Java program of the approach
import java.util.*;
class GFG
{
// initializing the max value
static final int MAX_SIZE = 1000005;
// To store all prime numbers
static Vector<Integer> primes = new Vector<Integer>();
// Function to generate N prime numbers using
// Sieve of Eratosthenes
static void SieveOfEratosthenes(Vector<Integer> primes)
{
// Create a boolean array "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true. A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
boolean[] IsPrime = new boolean[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for (int p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed, then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.add(p);
}
static void printLevel(int level)
{
System.out.print("primes at level " + level + ": ");
int left_index = (int) Math.pow(2, level - 1);
int right_index = (int) (Math.pow(2, level) - 1);
for (int i = left_index; i <= right_index; i++)
{
System.out.print(primes.get(i - 1) + " ");
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
// Function call
SieveOfEratosthenes(primes);
printLevel(1);
printLevel(2);
printLevel(3);
printLevel(4);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program of the approach
MAX_SIZE = 1000005
primes = []
# Function to generate N prime numbers using
# Sieve of Eratosthenes
def SieveOfEratosthenes():
# Create a boolean array "IsPrime[0..MAX_SIZE]" and
# initialize all entries it as True. A value in
# IsPrime[i] will finally be false if i is
# Not a IsPrime, else True.
IsPrime = [True] * MAX_SIZE
p = 2
while p * p < MAX_SIZE:
# If IsPrime[p] is not changed, then it is a prime
if (IsPrime[p] == True):
# Update all multiples of p greater than or
# equal to the square of it
# numbers which are multiple of p and are
# less than p^2 are already been marked.
for i in range(p * p, MAX_SIZE, p):
IsPrime[i] = False
p += 1
# Store all prime numbers
for p in range(2, MAX_SIZE):
if (IsPrime[p]):
primes.append(p)
def printLevel(level):
print("primes at level ", level, ":", end=" ")
left_index = pow(2, level - 1)
right_index = pow(2, level) - 1
for i in range(left_index, right_index + 1):
print(primes[i - 1], end=" ")
print()
# Driver Code
# Function call
SieveOfEratosthenes()
printLevel(1)
printLevel(2)
printLevel(3)
printLevel(4)
# This code is contributed by mohit kumar 29
C#
// C# program of the approach
using System;
using System.Collections.Generic;
class GFG
{
// initializing the max value
static readonly int MAX_SIZE = 1000005;
// To store all prime numbers
static List<int> primes = new List<int>();
// Function to generate N prime numbers using
// Sieve of Eratosthenes
static void SieveOfEratosthenes(List<int> primes)
{
// Create a bool array "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true. A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
bool[] IsPrime = new bool[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for (int p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed, then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.Add(p);
}
static void printLevel(int level)
{
Console.Write("primes at level " + level + ": ");
int left_index = (int) Math.Pow(2, level - 1);
int right_index = (int) (Math.Pow(2, level) - 1);
for (int i = left_index; i <= right_index; i++)
{
Console.Write(primes[i - 1] + " ");
}
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
// Function call
SieveOfEratosthenes(primes);
printLevel(1);
printLevel(2);
printLevel(3);
printLevel(4);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program of the approach
// Initializing the max value
let MAX_SIZE = 1000005
// To store all prime numbers
let primes = new Array();
// Function to generate N prime numbers using
// Sieve of Eratosthenes
function SieveOfEratosthenes(primes)
{
// Create a boolean array "IsPrime[0..MAX_SIZE]" and
// initialize all entries it as true. A value in
// IsPrime[i] will finally be false if i is
// Not a IsPrime, else true.
let IsPrime = new Array(MAX_SIZE).fill(true);
for(let p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed,
// then it is a prime
if (IsPrime[p] == true)
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for(let i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
// Store all prime numbers
for(let p = 2; p < MAX_SIZE; p++)
if (IsPrime[p])
primes.push(p);
}
function printLevel(level)
{
document.write("primes at level " +
level + ": ");
let left_index = Math.pow(2, level - 1);
let right_index = Math.pow(2, level) - 1;
for(let i = left_index; i <= right_index; i++)
{
document.write(primes[i - 1] + " ");
}
document.write("<br>");
}
// Driver Code
// Function call
SieveOfEratosthenes(primes);
printLevel(1);
printLevel(2);
printLevel(3);
printLevel(4);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
primes at level 1: 2 primes at level 2: 3 5 primes at level 3: 7 11 13 17 primes at level 4: 19 23 29 31 37 41 43 47
Publicación traducida automáticamente
Artículo escrito por ShrabanaBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA