Encuentre el número mínimo de valor de registro necesario para calcular el registro hasta N

Dado un número entero N. La tarea es encontrar el número mínimo de valores logarítmicos necesarios para calcular todos los valores logarítmicos de 1 a N utilizando las propiedades del logaritmo.
Ejemplos :

Input : N = 6
Output : 3
Value of log1 is already know, i.e. 0.
Except this the three log values needed are,
log2, log3, log5.

Input : N = 4
Output : 2

Una de las propiedades de la función de registro es:

log(x.y) = log(x) + log(y)

Por lo tanto, para calcular log(xy), debemos conocer los valores logarítmicos de x e y. Entendamos el concepto usando un ejemplo, para N = 6. Sea ans el número de valores logarítmicos necesarios para encontrar todos los valores logarítmicos del 1 al 6.

log(1)=0 (implícito).
Para calcular log(2), debemos conocer su valor antes, no podemos encontrarlo usando la propiedad. Entonces, ans se convierte en 1.
Para calcular log(3), debemos conocer su valor antes, no podemos encontrarlo usando la propiedad. Entonces, ans se convierte en 2.
Para calcular log(4), podemos usar la propiedad, log(4)=log(2.2)=log(2)+log(2). Como ya encontramos log(2), entonces ans sigue siendo 2.
Para calcular log(5), debemos conocer su valor antes, no podemos encontrarlo usando la propiedad. Entonces, ans se convierte en 3.
Para calcular log(6), podemos usar la propiedad, log(6)=log(2.3)=log(2)+log(3). Como ya encontramos log(2) y log(3), por lo tanto, ans sigue siendo 3 .

La idea es muy simple, al observar detenidamente, encontrará que no puede calcular los valores logarítmicos de un número primo, ya que no tiene divisor (aparte de 1 y él mismo). Entonces, la tarea se reduce a encontrar todos los números primos del 1 al N.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find number of log values
// needed to calculate all the log values
// from 1 to N
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000005
 
// In this vector prime[i] will store true
// if prime[i] is prime, else store false
vector<bool> prime(MAX, true);
 
// Using sieve of Eratosthenes to find
// all prime upto N
void sieve(int N)
{
    prime[0] = prime[1] = false;
     
    for (int i = 2; i <= N; i++) {
        if (prime[i]) {
            for (int j = 2; i * j <= N; j++)
                prime[i * j] = false;
        }
    }
}
 
// Function to find number of log values needed
// to calculate all the log values from 1 to N
int countLogNeeded(int N)
{
    int count = 0;
     
    // calculate primes upto N
    sieve(N);
     
    for (int i = 1; i <= N; i++) {
        if (prime[i])
            count++;
    }
     
    return count;
}
 
// Driver code
int main()
{
    int N = 6;
     
    cout<<countLogNeeded(N)<<endl;
     
    return 0;
}

Java

// Java program to find number of log values
// needed to calculate all the log values
// from 1 to N
import java.util.*;
 
class GFG
{
 
    static int MAX = 1000005;
 
    // In this vector prime[i] will store true
    // if prime[i] is prime, else store false
    static Vector<Boolean> prime = new Vector<>(MAX);
 
    static void vecIni()
    {
        for (int i = 0; i < MAX; i++)
        {
            prime.add(i, true);
        }
    }
 
    // Using sieve of Eratosthenes to find
    // all prime upto N
    static void sieve(int N)
    {
        prime.add(0, false);
        prime.add(1, false);
 
        for (int i = 2; i <= N; i++)
        {
            if (prime.get(i))
            {
                for (int j = 2; i * j <= N; j++)
                {
                    prime.add(i * j, false);
                }
            }
        }
    }
 
    // Function to find number of log values needed
    // to calculate all the log values from 1 to N
    static int countLogNeeded(int N)
    {
        int count = 0;
 
        // calculate primes upto N
        sieve(N);
 
        for (int i = 1; i <= N; i++)
        {
            if (prime.get(i))
            {
                count++;
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        vecIni();
        int N = 6;
        System.out.println(countLogNeeded(N));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to find number of log values
# needed to calculate all the log values
# from 1 to N
 
MAX = 1000005
 
# In this list prime[i] will store true
# if prime[i] is prime, else store false
prime = [True for i in range(MAX)]
 
# Using sieve of Eratosthenes to find
# all prime upto N
def sieve(N):
 
    prime[0], prime[1] = False, False
 
    for i in range(2, N + 1):
        if(prime[i]):
            for j in range(2, N + 1):
                if(i * j > N):
                    break
                prime[i * j] = False
 
 
# Function to find number of log values needed
# to calculate all the log values from 1 to N
def countLogNeeded(N):
 
    count = 0
 
    # calculate primes upto N
    sieve(N)
 
    for i in range(1, N + 1):
        if(prime[i]):
            count = count + 1
 
    return count
 
# Driver code
if __name__=='__main__':
    N = 6
    print(countLogNeeded(N))
 
# This code is contributed by
# Sanjit_Prasad

C#

// C# program to find number of log values
// needed to calculate all the log values
// from 1 to N
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
 
    static int MAX = 1000005;
 
    // In this vector prime[i] will store true
    // if prime[i] is prime, else store false
    static List<Boolean> prime = new List<Boolean>(MAX);
 
    static void vecIni()
    {
        for (int i = 0; i < MAX; i++)
        {
            prime.Add(true);
        }
    }
 
    // Using sieve of Eratosthenes to find
    // all prime upto N
    static void sieve(int N)
    {
        prime.Insert(0, false);
        prime.Insert(1, false);
 
        for (int i = 2; i <= N; i++)
        {
            if (prime[i])
            {
                for (int j = 2; i * j <= N; j++)
                {
                    prime.Insert(i * j, false);
                }
            }
        }
    }
 
    // Function to find number of log values needed
    // to calculate all the log values from 1 to N
    static int countLogNeeded(int N)
    {
        int count = 0;
 
        // calculate primes upto N
        sieve(N);
 
        for (int i = 1; i <= N; i++)
        {
            if (prime[i])
            {
                count++;
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        vecIni();
        int N = 6;
        Console.Write(countLogNeeded(N));
    }
}
 
/* This code contributed by Mohit kumar */

Javascript

<script>
 
// Javascript program to find number of log values
// needed to calculate all the log values
// from 1 to N
 
MAX = 1000005
 
// In this vector prime[i] will store true
// if prime[i] is prime, else store false
var prime = Array(MAX).fill(true);
 
// Using sieve of Eratosthenes to find
// all prime upto N
function sieve(N)
{
    prime[0] = prime[1] = false;
     
    for (var i = 2; i <= N; i++) {
        if (prime[i]) {
            for (var j = 2; i * j <= N; j++)
                prime[i * j] = false;
        }
    }
}
 
// Function to find number of log values needed
// to calculate all the log values from 1 to N
function countLogNeeded(N)
{
    var count = 0;
     
    // calculate primes upto N
    sieve(N);
     
    for (var i = 1; i <= N; i++) {
        if (prime[i])
            count++;
    }
     
    return count;
}
 
// Driver code
var N = 6;
 
document.write( countLogNeeded(N));
 
</script>

Producción:

Complejidad del Tiempo: $O(\sqrt{N} * log(log(N)))$
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta