Cuenta todos los números menores de 10^6 cuyo factor primo mínimo sea N

Dado un número N que es primo. La tarea es encontrar todos los números menores o iguales a 10^6 cuyo factor primo mínimo sea N.
Ejemplos: 
 

Input: N = 2
Output: 500000

Input: N = 3
Output: 166667

Planteamiento: Utilice el tamiz de Eratóstenes para encontrar la solución al problema. Almacena todos los números primos menores que 10^6. Forme otro tamiz que almacene el conteo de todos los números cuyo factor primo mínimo sea el índice del tamiz. Luego muestre la cuenta del número primo N (es decir, sieve_count[n]+1), donde n es el número primo.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
 
// the sieve of prime number and
// count of minimum prime factor
int sieve_Prime[MAX + 4] = { 0 },
                      sieve_count[MAX + 4] = { 0 };
 
// form the prime sieve
void form_sieve()
{
    // 1 is not a prime number
    sieve_Prime[1] = 1;
 
    // form the sieve
    for (int i = 2; i <= MAX; i++) {
 
        // if i is prime
        if (sieve_Prime[i] == 0) {
            for (int j = i * 2; j <= MAX; j += i) {
 
                // if i is the least prime factor
                if (sieve_Prime[j] == 0) {
 
                    // mark the number j as non prime
                    sieve_Prime[j] = 1;
 
                    // count the numbers whose least prime factor is i
                    sieve_count[i]++;
                }
            }
        }
    }
}
 
// Driver code
int main()
{
    // form the sieve
    form_sieve();
 
    int n = 2;
 
    // display
    cout << "Count = " << (sieve_count[n] + 1) << endl;
 
    n = 3;
 
    // display
    cout << "Count = " << (sieve_count[n] + 1) << endl;
 
    return 0;
}

// Java implementation of above approach
import java.io.*;
 
class GFG {
     
static int MAX = 1000000;
 
// the sieve of prime number and
// count of minimum prime factor
static int sieve_Prime[] = new int[MAX + 4];
static int sieve_count[] =  new int[MAX + 4];
 
// form the prime sieve
static void form_sieve()
{
    // 1 is not a prime number
    sieve_Prime[1] = 1;
 
    // form the sieve
    for (int i = 2; i <= MAX; i++) {
 
        // if i is prime
        if (sieve_Prime[i] == 0) {
            for (int j = i * 2; j <= MAX; j += i) {
 
                // if i is the least prime factor
                if (sieve_Prime[j] == 0) {
 
                    // mark the number j as non prime
                    sieve_Prime[j] = 1;
 
                    // count the numbers whose least prime factor is i
                    sieve_count[i]++;
                }
            }
        }
    }
}
 
// Driver code
 
    public static void main (String[] args) {
        // form the sieve
    form_sieve();
 
    int n = 2;
 
    // display
    System.out.println( "Count = " + (sieve_count[n] + 1));
 
    n = 3;
 
    // display
    System.out.println ("Count = "  +(sieve_count[n] + 1));
    }
}
// This code was contributed
// by inder_mca

# Python3 implementation of
# above approach
 
MAX = 1000000
 
# the sieve of prime number and
# count of minimum prime factor
sieve_Prime = [0 for i in range(MAX + 4)]
sieve_count = [0 for i in range(MAX + 4)]
 
# form the prime sieve
def form_sieve():
     
    # 1 is not a prime number
    sieve_Prime[1] = 1
 
    # form the sieve
    for i in range(2, MAX + 1):
 
        # if i is prime
        if sieve_Prime[i] == 0:
            for j in range(i * 2, MAX + 1, i):
 
                # if i is the least prime factor
                if sieve_Prime[j] == 0:
 
                    # mark the number j
                    # as non prime
                    sieve_Prime[j] = 1
 
                    # count the numbers whose
                    # least prime factor is i
                    sieve_count[i] += 1
 
# Driver code
 
# form the sieve
form_sieve()
 
n = 2
 
# display
print("Count =", sieve_count[n] + 1)
 
n = 3
 
# display
print("Count =", sieve_count[n] + 1)
 
# This code was contributed
# by VishalBachchas

// C# implementation of above approach
using System;
 
class GFG {
     
static int MAX = 1000000;
 
// the sieve of prime number and
// count of minimum prime factor
static int []sieve_Prime = new int[MAX + 4];
static int []sieve_count = new int[MAX + 4];
 
// form the prime sieve
static void form_sieve()
{
    // 1 is not a prime number
    sieve_Prime[1] = 1;
 
    // form the sieve
    for (int i = 2; i <= MAX; i++) {
 
        // if i is prime
        if (sieve_Prime[i] == 0) {
            for (int j = i * 2; j <= MAX; j += i) {
 
                // if i is the least prime factor
                if (sieve_Prime[j] == 0) {
 
                    // mark the number j as non prime
                    sieve_Prime[j] = 1;
 
                    // count the numbers whose least prime factor is i
                    sieve_count[i]++;
                }
            }
        }
    }
}
 
// Driver code
 
    public static void Main () {
        // form the sieve
    form_sieve();
 
    int n = 2;
 
    // display
    Console.WriteLine( "Count = " + (sieve_count[n] + 1));
 
    n = 3;
 
    // display
    Console.WriteLine ("Count = " +(sieve_count[n] + 1));
    }
}
// This code was contributed
// by shs

<?php
// PHP implementation of above approach
$MAX = 1000000;
 
// the sieve of prime number and
// count of minimum prime factor
$sieve_Prime = array_fill(0, $MAX + 4, NULL);
$sieve_count = array_fill(0, $MAX + 4, NULL);
 
// form the prime sieve
function form_sieve()
{
    global $sieve_Prime, $sieve_count, $MAX;
     
    // 1 is not a prime number
    $sieve_Prime[1] = 1;
 
    // form the sieve
    for ($i = 2; $i <= $MAX; $i++)
    {
 
        // if i is prime
        if ($sieve_Prime[$i] == 0)
        {
            for ($j = $i * 2; $j <= $MAX; $j += $i)
            {
 
                // if i is the least prime factor
                if ($sieve_Prime[$j] == 0)
                {
 
                    // mark the number j as non prime
                    $sieve_Prime[$j] = 1;
 
                    // count the numbers whose least
                    // prime factor is i
                    $sieve_count[$i]++;
                }
            }
        }
    }
}
 
// Driver code
 
// form the sieve
form_sieve();
 
$n = 2;
 
// display
echo "Count = " . ($sieve_count[$n] + 1) . "\n";
 
$n = 3;
 
// display
echo "Count = " . ($sieve_count[$n] + 1) . "\n";
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript implementation of above approach
    
var MAX = 1000000;
 
// the sieve of prime number and
// count of minimum prime factor
var sieve_Prime = Array.from({length: MAX + 4},
(_, i) => 0);
var sieve_count =  Array.from({length: MAX + 4},
(_, i) => 0);
 
// form the prime sieve
function form_sieve()
{
    // 1 is not a prime number
    sieve_Prime[1] = 1;
 
    // form the sieve
    for (i = 2; i <= MAX; i++) {
 
        // if i is prime
        if (sieve_Prime[i] == 0) {
            for (j = i * 2; j <= MAX; j += i) {
 
                // if i is the least prime factor
                if (sieve_Prime[j] == 0) {
 
                    // mark the number j as non prime
                    sieve_Prime[j] = 1;
 
                    // count the numbers whose least
                    // prime factor is i
                    sieve_count[i]++;
                }
            }
        }
    }
}
 
// Driver code
 
// form the sieve
form_sieve();
 
var n = 2;
 
// display
document.write( "Count = " + (sieve_count[n] + 1));
 
n = 3;
 
// display
document.write("<br>Count = "  +(sieve_count[n] + 1));
    
 
 
// This code contributed by shikhasingrajput
 
</script>

Count = 500000
Count = 166667

Complejidad de tiempo: O(N*log(log(N))), donde N=10 ⁶ .

Espacio Auxiliar: O(10 ⁶ )