Encuentra la posición del número primo dado

Dado un número N que es un número primo , la tarea es encontrar la posición del número primo dado en la serie de números primos.
Ejemplos: 
 

Entrada: N = 11 
Salida: 5 
Explicación: 
Los números primos son 2, 3, 5, 7, 11, 13, 17, …. 
Por lo tanto, la posición de 11 en esta serie es 5.
Entrada: N = 13 
Salida: 6 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es para la entrada dada, calcular los números primos que son menores que ese número y realizar un seguimiento del número de primos menores que el N dado . Si el conteo es K , entonces K + 1 sería la respuesta. La complejidad temporal para este enfoque es cuadrática. 
Enfoque eficiente: la idea es utilizar la ligera modificación de Tamiz de Eratóstenes. Todos los números primos hasta el valor máximo se pueden calcular y almacenar en una array junto con su posición. Claramente, cuando los números primos se almacenan en una array, el índice en el que se almacena el número es la posición del número en la serie. Después de este cálculo previo, la respuesta se puede calcular en tiempo constante. 
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the position
// of the given prime number
 
#include <bits/stdc++.h>
#define limit 10000000
using namespace std;
int position[limit + 1];
 
// Function to precompute the position
// of every prime number using Sieve
void sieve()
{
    // 0 and 1 are not prime numbers
    position[0] = -1, position[1] = -1;
 
    // Variable to store the position
    int pos = 0;
    for (int i = 2; i <= limit; i++) {
        if (position[i] == 0) {
 
            // Incrementing the position for
            // every prime number
            position[i] = ++pos;
            for (int j = i * 2; j <= limit; j += i)
                position[j] = -1;
        }
    }
}
 
// Driver code
int main()
{
    sieve();
 
    int n = 11;
    cout << position[n];
    return 0;
}

// Java program to find the position
// of the given prime number
class GFG{   
     
static final int limit = 10000000;
static int []position = new int[limit + 1];
  
// Function to precompute the position
// of every prime number using Sieve
static void sieve()
{
    // 0 and 1 are not prime numbers
    position[0] = -1;
    position[1] = -1;
  
    // Variable to store the position
    int pos = 0;
    for (int i = 2; i <= limit; i++) {
        if (position[i] == 0) {
  
            // Incrementing the position for
            // every prime number
            position[i] = ++pos;
            for (int j = i * 2; j <= limit; j += i)
                position[j] = -1;
        }
    }
}
  
// Driver code
public static void main(String[] args)
{
    sieve();
  
    int n = 11;
    System.out.print(position[n]);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find the position
# of the given prime number
limit = 1000000
position = [0]*(limit + 1)
  
# Function to precompute the position
# of every prime number using Sieve
def sieve():
 
    # 0 and 1 are not prime numbers
    position[0] = -1
    position[1] = -1
  
    # Variable to store the position
    pos = 0
    for i in range(2, limit + 1):
        if (position[i] == 0):
  
            # Incrementing the position for
            # every prime number
            pos += 1
            position[i] = pos
            for j in range( i * 2, limit + 1 ,i):
                position[j] = -1
  
# Driver code
if __name__ == "__main__":
    sieve()
  
    n = 11
    print(position[n])
     
# This code is contributed by chitranayal

// C# program to find the position
// of the given prime number
using System;
 
class GFG{   
      
static readonly int limit = 1000000;
static int []position = new int[limit + 1];
   
// Function to precompute the position
// of every prime number using Sieve
static void sieve()
{
    // 0 and 1 are not prime numbers
    position[0] = -1;
    position[1] = -1;
   
    // Variable to store the position
    int pos = 0;
    for (int i = 2; i <= limit; i++) {
        if (position[i] == 0) {
   
            // Incrementing the position for
            // every prime number
            position[i] = ++pos;
            for (int j = i * 2; j <= limit; j += i)
                position[j] = -1;
        }
    }
}
   
// Driver code
public static void Main(String[] args)
{
    sieve();
   
    int n = 11;
    Console.Write(position[n]);
}
}
  
// This code is contributed by Princi Singh

<script>
 
// Javascript program to find the position
// of the given prime number
var limit = 10000000
var position = Array(limit+1).fill(0);
 
// Function to precompute the position
// of every prime number using Sieve
function sieve()
{
 
    // 0 and 1 are not prime numbers
    position[0] = -1, position[1] = -1;
 
    // Variable to store the position
    var pos = 0;
    for (var i = 2; i <= limit; i++)
    {
        if (position[i] == 0)
        {
 
            // Incrementing the position for
            // every prime number
            position[i] = ++pos;
            for (var j = i * 2; j <= limit; j += i)
                position[j] = -1;
        }
    }
}
 
// Driver code
sieve();
var n = 11;
document.write( position[n]);
 
// This code is contributed by noob2000.
</script>

5

Complejidad de tiempo: O (límite ² )

Espacio auxiliar: O (límite)