Número de enteros sin marcar en un tamiz especial

Dada una array A que contiene números del 2 al N. . En él se realiza un tipo especial de tamizado. 
El procedimiento de tamizado es el siguiente: 
 

1. Cree una array con elementos como enteros consecutivos del 2 al N y marque cada elemento de la array como sin marcar.
2. Sea un entero Q = N y marque todos los divisores propios de Q excepto Q en el arreglo.
3. Encuentre el número más grande sin marcar menor que Q y asígnele Q, y repita desde el paso 2. Si no hay más elementos sin marcar, deténgase.

Encuentre el número de enteros sin marcar después de tamizar.
Ejemplos: 
 

Input : N = 5 
Output : Number of unmarked elements = 3
Explanation : We create array A[] = { 2, 3, 4, 5 }.
2 is marked as it is a proper divisor of 4.

Input : N = 4
Output : Number of unmarked elements = 2

Enfoque ingenuo: 
un enfoque básico es ejecutar dos bucles. Bucle externo para atravesar toda la array y bucle interno para atravesar desde 2 – Q para desmarcar todos los divisores adecuados de Q al verificar a[i] % Q = 0.
Complejidad de tiempo: O(N^2)
Enfoque eficiente: 
una simple observación sugiere que en realidad no hay necesidad de tamizar aquí, sino que el valor de N determinará la respuesta. 
Caso 1: si N es impar , el número de elementos sin marcar será (N/2) + 1.
Caso 2: si N es par , el número de elementos sin marcar será (N/2).
Complejidad temporal: O(1)
Ejemplos: 
 

Entrada: N = 5 
Salida: 3 
A[] = { 2, 3, 4, 5 } 
Pasos: 
1.) Q = 5: Marque todos los divisores adecuados de Q, aquí no hay ningún elemento, por lo que cada elemento permanece sin marcar. 
3.) Q = 4: Marque todos los divisores propios de Q. Aquí 2 se marca y los elementos sin marcar son {3, 4, 5}. 
5.) Q = 3: 
6.) Ahora no se pueden marcar más, así que deténgase aquí. 
Así que el número de elementos no marcados es 3, es decir, {3, 4, 5} 
En caso de que el valor de N sea IMPAR, el resultado debería ser (N/2) +1 = (3/2)+1 = (5/2)+1 = 2+1= 3.
Entrada: N = 4 
Salida: 2 
A[] = { 2, 3, 4 } 
Pasos: 
1.) Q = 4 Marque todos los divisores propios de Q. Así que aquí 2 se marca y los elementos sin marcar son {3, 4} 
3.) Q = 3 
4.) Ahora no se pueden marcar más, así que deténgase aquí. 
Por lo tanto, el número de elementos no marcados después del tamizado es {3, 4} = 2. 
En caso de que el valor de N sea PAR, el resultado debe ser (N/2) = (4/2) = 2
 

// C++ Program to determine the
// number of unmarked integers in
// a special sieve
#include <bits/stdc++.h>
using namespace std;
 
int countUnmarked(int N)
{
    if (N % 2 == 0)
       return N/2;
    else
       return N/2 + 1;
}
 
// Driver Code
int main()
{
    int N = 4;
    cout << "Number of unmarked elements: "
         << countUnmarked(N) << endl;
    return 0;
}

// Java Program to determine
// the number of unmarked
// integers in a special sieve
import java.io.*;
 
class GFG
{
static int countUnmarked(int N)
{
    if (N % 2 == 0)
    return N / 2;
    else
    return N / 2 + 1;
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 4;
    System.out.println("Number of unmarked " +
                                "elements: " +
                            countUnmarked(N));
}
}
 
// This code is contributed
// by anuj_67.

# Python3 Program to determine
# the number of unmarked
# integers in a special sieve
def countUnmarked(N):
    if (N % 2 == 0):
        return N / 2;
    else:
        return N / 2 + 1;
 
# Driver Code
N = 4;
print("Number of unmarked elements:",
              int(countUnmarked(N)));
     
# This code is contributed
# by mits

// C# Program to determine
// the number of unmarked
// integers in a special sieve
using System;
 
class GFG
{
static int countUnmarked(int N)
{
    if (N % 2 == 0)
        return N / 2;
    else
        return N / 2 + 1;
}
 
// Driver Code
public static void Main ()
{
    int N = 4;
    Console.WriteLine("Number of unmarked " +
                               "elements: " +
                           countUnmarked(N));
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP Program to determine
// the number of unmarked
// integers in a special sieve
 
function countUnmarked($N)
{
    if ($N % 2 == 0)
    return $N / 2;
    else
    return $N / 2 + 1;
}
 
// Driver Code
$N = 4;
echo "Number of unmarked elements: ",
                   countUnmarked($N);
     
// This code is contributed
// by anuj_67.
?>

<script>
// javascript Program to determine
// the number of unmarked
// integers in a special sieve
    function countUnmarked(N) {
        if (N % 2 == 0)
            return N / 2;
        else
            return N / 2 + 1;
    }
 
    // Driver Code
     
        var N = 4;
        document.write("Number of unmarked "
        + "elements: " + countUnmarked(N));
 
// This code is contributed by todaysgaurav
</script>

Number of unmarked elements: 2