Recuento de enteros hasta N que no son divisores ni coprimos con N

Dado un número entero N , la tarea es encontrar el recuento de todos los números enteros posibles menores que N que satisfagan las siguientes propiedades:

• El número no es coprimo con N , es decir, su GCD es mayor que 1.
• El número no es divisor de N.

Ejemplos:

Entrada: N = 10 
Salida: 3 
Explicación: 
Todos los enteros posibles que son menores que 10 y no son ni divisores ni coprimos con 10, son {4, 6, 8}. 
Por lo tanto, el conteo requerido es 3.
Entrada: N = 42 
Salida: 23

Enfoque: 
siga los pasos a continuación para resolver el problema:

• Establecer cuenta = N .
• Calcule la función Totient de Euler para todos los valores hasta N para encontrar el número de números en el rango [1, N] que son coprimos con N , es decir, los números cuyo MCD (máximo común divisor) con N es 1.
• Dado que estos son coprimos con N , restarlos de la cuenta .
• Calcular el conteo de divisores de N usando la Criba de Eratóstenes . Restarlos de la cuenta .
• Imprime el valor final de count que es igual a:

Recuento total = N – totient de Euler (N) – Recuento de divisor (N)

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of integers less than N
// satisfying given conditions
int count(int n)
{
    // Stores Euler counts
    int phi[n + 1] = { 0 };
 
    // Store Divisor counts
    int divs[n + 1] = { 0 };
 
    // Based on Sieve of Eratosthenes
    for (int i = 1; i <= n; i++) {
 
        phi[i] += i;
 
        // Update phi values of all
        // multiples of i
        for (int j = i * 2; j <= n; j += i)
            phi[j] -= phi[i];
 
        // Update count of divisors
        for (int j = i; j <= n; j += i)
            divs[j]++;
    }
 
    // Return the final count
    return (n - phi[n] - divs[n] + 1);
}
 
// Driver Code
int main()
{
 
    int N = 42;
 
    cout << count(N);
    return 0;
}

// Java program to implement
// the above approach
import java.util.Arrays;
 
class GFG{
     
// Function to return the count
// of integers less than N
// satisfying given conditions
public static int count(int n)
{
     
    // Stores Euler counts
    int []phi = new int[n + 1];
    Arrays.fill(phi, 0);
 
    // Store Divisor counts
    int []divs = new int[n + 1];
    Arrays.fill(divs, 0);
     
    // Based on Sieve of Eratosthenes
    for(int i = 1; i <= n; i++)
    {
        phi[i] += i;
 
        // Update phi values of all
        // multiples of i
        for(int j = i * 2; j <= n; j += i)
            phi[j] -= phi[i];
 
        // Update count of divisors
        for(int j = i; j <= n; j += i)
            divs[j]++;
    }
 
    // Return the final count
    return (n - phi[n] - divs[n] + 1);
}
 
// Driver Code
public static void main(String []args)
{
    int N = 42;
 
    System.out.println(count(N));
}
}
 
// This code is contributed by grand_master

# Python3 program to implement
# the above approach
 
# Function to return the count
# of integers less than N
# satisfying given conditions
def count(n):
     
    # Stores Euler counts
    phi = [0] * (n + 1)
     
    # Store Divisor counts
    divs = [0] * (n + 1)
     
    # Based on Sieve of Eratosthenes
    for i in range(1, n + 1):
        phi[i] += i
         
        # Update phi values of all
        # multiples of i
        for j in range(i * 2, n + 1, i):
            phi[j] -= phi[i];
 
        # Update count of divisors
        for j in range(i, n + 1, i):
            divs[j] += 1
             
    # Return the final count
    return (n - phi[n] - divs[n] + 1);
     
# Driver code
if __name__ == '__main__':
     
    N = 42
     
    print(count(N))
 
# This code is contributed by jana_sayantan

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to return the count
// of integers less than N
// satisfying given conditions
public static int count(int n)
{
     
    // Stores Euler counts
    int []phi = new int[n + 1];
     
    // Store Divisor counts
    int []divs = new int[n + 1];
     
    // Based on Sieve of Eratosthenes
    for(int i = 1; i <= n; i++)
    {
        phi[i] += i;
 
        // Update phi values of all
        // multiples of i
        for(int j = i * 2; j <= n; j += i)
            phi[j] -= phi[i];
 
        // Update count of divisors
        for(int j = i; j <= n; j += i)
            divs[j]++;
    }
 
    // Return the final count
    return (n - phi[n] - divs[n] + 1);
}
 
// Driver Code
public static void Main(String []args)
{
    int N = 42;
 
    Console.WriteLine(count(N));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the above approach
 
// Function to return the count
// of integers less than N
// satisfying given conditions
function count(n)
{
       
    // Stores Euler counts
    let phi = [];
       
    // Store Divisor counts
    let divs = [];
    for(let i = 1; i <= n; i++)
    {
        phi[i] = 0;
        divs[i] = 0;
    }
       
    // Based on Sieve of Eratosthenes
    for(let i = 1; i <= n; i++)
    {
        phi[i] += i;
   
        // Update phi values of all
        // multiples of i
        for(let j = i * 2; j <= n; j += i)
            phi[j] -= phi[i];
   
        // Update count of divisors
        for(let j = i; j <= n; j += i)
            divs[j]++;
    }
   
    // Return the final count
    return (n - phi[n] - divs[n] + 1);
}
 
// Driver code
         
        let N = 42;
   document.write(count(N));
       
    // This code is contributed by code_hunt.
</script>

23

Complejidad de tiempo: O(N*log(log(N))) 
Espacio auxiliar: O(N)