Cuenta números hasta N cuyo MCD con N es menor que ese número

Dado un número entero N , la tarea es contar los valores de K ( donde 1 ≤ K≤ N ), tal que 1< GCD (K, N) < K.

Ejemplos:

Entrada: N = 10
Salida: 3
Explicación: Los valores de K que satisfacen las condiciones dadas son: 

• K = 4, mcd(4, 10) = 2
• K = 6, mcd(6, 10) = 2
• K = 8, mcd(8, 10) = 2

Entrada: N = 15
Salida: 4
Explicación: Los valores de K que satisfacen las condiciones dadas son: 

• K = 6, mcd(6, 15) = 3
• K = 9, mcd(9, 15) = 3
• K = 10, mcd(10, 15) = 5
• K = 12, mcd(12, 15) = 3

Enfoque ingenuo: el enfoque más simple es iterar sobre el rango [1, N] y verificar cada número, ya sea que satisfaga la condición dada o no. Finalmente, imprima el conteo de dichos números.

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

Enfoque eficiente: la idea es encontrar todos los números en el rango [1, N] , para los cuales mcd(K, N) = 1 y mcd(K, N) = K y luego eliminar todos estos números de N para obtener la respuesta final Siga los pasos a continuación para resolver el problema:

• Almacene todos los factores primos de N usando la criba de Eratóstenes.
• Almacene el conteo de todos los números en el rango [1, N] para el cual mcd(N, K) = K en una variable conteo1 .
• Almacene el conteo de todos los números en el rango [1, N] para los cuales mcd(N, K) = 1 usando la función Totient de Euler en una variable conteo2 .
• Elimine estos números de N , actualizando ans a N – (count1 + count2) .
• Imprime el valor de ans como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Store the all prime numbers
// using Sieve of Eratosthenes
const int MAXN = 100001;
vector<int> spf;
 
// Function to fill the prime numbers
// using Sieve of Eratosthenes
void sieve()
{
    // Create a boolean array and
    // initialize all entries it as 0
    int p[MAXN + 1] = { 0 };
 
    p[2] = 1;
    for (long long int i = 3; i < MAXN; i += 2) {
        p[i] = 1;
    }
 
    // Push the first prime number
    spf.push_back(2);
 
    for (long long i = 3; i < MAXN; i += 2) {
 
        // If the current number is prime
        if (p[i]) {
 
            // Store the prime numbers
            // in spf which is prime
            spf.push_back(i);
 
            // Mark all its multiples as false
            for (long long int j = i * i; j < MAXN;
                 j += 2 * i)
                p[j] = 0;
        }
    }
}
 
// Function to count the values of K where
// 1≤K≤N such that 1< gcd(K, N) < K
void countK(int N)
{
    // Precalculate prime numbers
    sieve();
    int N1 = N;
 
    // Store the smallest prime number
    int div = spf[0];
 
    int index = 1, C = 0;
 
    // Store the count of those numbers in the
    // range [1, N] for which gcd(N, K) = K
    int count1 = 1;
 
    // Store the count of those numbers from
    // the range [1, N] such that gcd(N, K) = 1
    float count2 = N;
 
    // Iterate through all prime factors of N
    while (div * div <= N) {
        if (N % div == 0) {
            C = 0;
            while (N % div == 0) {
                N /= div;
                C++;
            }
 
            count1 = count1 * (C + 1);
 
            // count2 is determined by
            // Euler's Totient Function
            count2 *= (1.0 - (1.0 / (float)div));
        }
 
        div = spf[index];
 
        index++;
    }
    if (N != 1) {
 
        count1 *= 2;
        count2 = count2 * (1.0 - (1.0 / (float)N));
    }
 
    int ans = N1 - count1 - count2;
 
    // Add 1 to result as 1 is contributed
    // twice due to count1 and count2
    ans = ans + 1;
 
    // Print the result
    cout << ans;
 
    return;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 10;
 
    // Function Call
    countK(N);
 
    return 0;
}

# Python3 program for the above approach
 
# Store the all prime numbers
# using Sieve of Eratosthenes
MAXN = 100001
spf = []
 
# Function to fill the prime numbers
# using Sieve of Eratosthenes
def sieve():
     
    global MAXN
     
    # Create a boolean array and
    # initialize all entries it as 0
    p = [0] * (MAXN + 1)
    p[2] = 1
     
    for i in range(3, MAXN, 2):
        p[i] = 1
 
    # Push the first prime number
    spf.append(2)
 
    for i in range(3, MAXN, 2):
         
        # If the current number is prime
        if (p[i]):
 
            # Store the prime numbers
            # in spf which is prime
            spf.append(i)
 
            # Mark all its multiples as false
            for j in range(i * i, MAXN, 2 * i):
                p[j] = 0
 
# Function to count the values of K where
# 1≤K≤N such that 1< gcd(K, N) < K
def countK(N):
     
    # Precalculate prime numbers
    sieve()
    N1 = N
 
    # Store the smallest prime number
    div = spf[0]
 
    index, C = 1, 0
 
    # Store the count of those numbers in the
    # range [1, N] for which gcd(N, K) = K
    count1 = 1
 
    # Store the count of those numbers from
    # the range [1, N] such that gcd(N, K) = 1
    count2 = N
 
    # Iterate through all prime factors of N
    while (div * div <= N):
        if (N % div == 0):
            C = 0
             
            while (N % div == 0):
                N //= div
                C += 1
 
            count1 = count1 * (C + 1)
 
            # count2 is determined by
            # Euler's Totient Function
            count2 *= (1.0 - (1.0 / div))
 
        div = spf[index]
 
        index += 1
 
    if (N != 1):
        count1 *= 2
        count2 = count2 * (1.0 - (1.0 / N))
 
    ans = N1 - count1 - count2
 
    # Add 1 to result as 1 is contributed
    # twice due to count1 and count2
    ans = ans + 1
 
    # Print the result
    print(int(ans))
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    N = 10
 
    # Function Call
    countK(N)
 
# This code is contributed by mohit kumar 29

<script>
 
// Javascript program for the above approach
 
// Store the all prime numbers
// using Sieve of Eratosthenes
var MAXN = 100001;
var spf = [];
 
// Function to fill the prime numbers
// using Sieve of Eratosthenes
function sieve()
{
 
// Create a boolean array and
    // initialize all entries it as 0
    var p = Array(MAXN + 1).fill(0);
 
    p[2] = 1;
    for (var i = 3; i < MAXN; i += 2) {
        p[i] = 1;
    }
 
    // Push the first prime number
    spf.push(2);
 
    for (var i = 3; i < MAXN; i += 2) {
 
        // If the current number is prime
        if (p[i]) {
 
            // Store the prime numbers
            // in spf which is prime
            spf.push(i);
 
            // Mark all its multiples as false
            for (var j = i * i; j < MAXN;
                 j += 2 * i)
                p[j] = 0;
        }
    }
}
 
// Function to count the values of K where
// 1≤K≤N such that 1< gcd(K, N) < K
function countK(N)
{
    // Precalculate prime numbers
    sieve();
    var N1 = N;
 
    // Store the smallest prime number
    var div = spf[0];
 
    var index = 1, C = 0;
 
    // Store the count of those numbers in the
    // range [1, N] for which gcd(N, K) = K
    var count1 = 1;
 
    // Store the count of those numbers from
    // the range [1, N] such that gcd(N, K) = 1
    var count2 = N;
 
    // Iterate through all prime factors of N
    while (div * div <= N) {
        if (N % div == 0) {
            C = 0;
            while (N % div == 0) {
                N /= div;
                C++;
            }
 
            count1 = count1 * (C + 1);
 
            // count2 is determined by
            // Euler's Totient Function
            count2 *= (1.0 - (1.0 / div));
        }
 
        div = spf[index];
 
        index++;
    }
    if (N != 1) {
 
        count1 *= 2;
        count2 = count2 * (1.0 - (1.0 / N));
    }
 
    var ans = N1 - count1 - count2;
 
    // Add 1 to result as 1 is contributed
    // twice due to count1 and count2
    ans = ans + 1;
 
    // Print the result
    document.write(ans);
 
    return;
}
 
// Driver Code
// Given Input
var N = 10;
 
// Function Call
countK(N);
 
// This code is contributed by rutvik_56.
</script>

3

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