Cuente números en el rango de 1 a N que son divisibles por X pero no por Y

Dados dos enteros positivos X e Y, la tarea es contar los números totales en el rango de 1 a N que son divisibles por X pero no por Y.

Ejemplos:

Entrada: x = 2, Y = 3, N = 10
Salida: 4
Los números divisibles por 2 pero no por 3 son: 2, 4, 8, 10

Entrada: X = 2, Y = 4, N = 20
Salida: 5
Los números divisibles por 2 pero no por 4 son: 2, 6, 10, 14, 18

Una solución simple es contar números divisibles por X pero no por Y es pasar de 1 a N y contar el número que es divisible por X pero no por Y.

Acercarse

Para cada número en el rango de 1 a N, Incremente el conteo si el número es divisible por X pero no por Y.
Imprime el conteo.

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

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count total numbers divisible by
// x but not y in range 1 to N
int countNumbers(int X, int Y, int N)
{
    int count = 0;
    for (int i = 1; i <= N; i++) {
        // Check if Number is divisible
        // by x but not Y
        // if yes, Increment count
        if ((i % X == 0) && (i % Y != 0))
            count++;
    }
    return count;
}
  
// Driver Code
int main()
{
  
    int X = 2, Y = 3, N = 10;
    cout << countNumbers(X, Y, N);
    return 0;
}

Java

// Java implementation of above approach
  
class GFG {
  
    // Function to count total numbers divisible by
    // x but not y in range 1 to N
    static int countNumbers(int X, int Y, int N)
    {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            // Check if Number is divisible
            // by x but not Y
            // if yes, Increment count
            if ((i % X == 0) && (i % Y != 0))
                count++;
        }
        return count;
    }
  
    // Driver Code
    public static void main(String[] args)
    {
  
        int X = 2, Y = 3, N = 10;
        System.out.println(countNumbers(X, Y, N));
    }
}

Python3

# Python3 implementation of above approach 
  
# Function to count total numbers divisible 
# by x but not y in range 1 to N 
def countNumbers(X, Y, N): 
  
    count = 0; 
    for i in range(1, N + 1):
          
        # Check if Number is divisible 
        # by x but not Y 
        # if yes, Increment count 
        if ((i % X == 0) and (i % Y != 0)): 
            count += 1; 
  
    return count; 
  
# Driver Code 
X = 2;
Y = 3;
N = 10; 
print(countNumbers(X, Y, N)); 
      
# This code is contributed by mits

C#

// C# implementation of the above approach
using System;
class GFG {
  
    // Function to count total numbers divisible by
    // x but not y in range 1 to N
    static int countNumbers(int X, int Y, int N)
    {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            // Check if Number is divisible
            // by x but not Y
            // if yes, Increment count
            if ((i % X == 0) && (i % Y != 0))
                count++;
        }
        return count;
    }
  
    // Driver Code
    public static void Main()
    {
  
        int X = 2, Y = 3, N = 10;
        Console.WriteLine(countNumbers(X, Y, N));
    }
}

PHP

<?php
//PHP implementation of above approach 
  
// Function to count total numbers divisible by 
// x but not y in range 1 to N 
function countNumbers($X, $Y, $N) 
{ 
    $count = 0; 
    for ($i = 1; $i <= $N; $i++)
    { 
        // Check if Number is divisible 
        // by x but not Y 
        // if yes, Increment count 
        if (($i % $X == 0) && ($i % $Y != 0)) 
            $count++; 
    } 
    return $count; 
} 
  
// Driver Code 
$X = 2;
$Y = 3;
$N = 10; 
echo (countNumbers($X, $Y, $N)); 
      
// This code is contributed by Arnab Kundu
?>

Producción:

Complejidad de tiempo : O(N)

Solución eficiente:

En el rango de 1 a N, encuentre los números totales divisibles por X y los números totales divisibles por Y .
Además, encuentre números totales divisibles por X o Y
Calcular el número total divisible por X pero no por Y como
(número total divisible por X o Y) – (número total divisible por Y)

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

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count total numbers divisible by
// x but not y in range 1 to N
int countNumbers(int X, int Y, int N)
{
  
    // Count total number divisible by X
    int divisibleByX = N / X;
  
    // Count total number divisible by Y
    int divisibleByY = N / Y;
  
    // Count total number divisible by either X or Y
    int LCM = (X * Y) / __gcd(X, Y);
    int divisibleByLCM = N / LCM;
    int divisibleByXorY = divisibleByX + divisibleByY 
                                     - divisibleByLCM;
  
    // Count total numbers divisible by X but not Y
    int divisibleByXnotY = divisibleByXorY 
                                       - divisibleByY;
  
    return divisibleByXnotY;
}
  
// Driver Code
int main()
{
  
    int X = 2, Y = 3, N = 10;
    cout << countNumbers(X, Y, N);
    return 0;
}

Java

// Java implementation of above approach
  
class GFG {
  
    // Function to calculate GCD
  
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
  
    // Function to count total numbers divisible by
    // x but not y in range 1 to N
  
    static int countNumbers(int X, int Y, int N)
    {
  
        // Count total number divisible by X
        int divisibleByX = N / X;
  
        // Count total number divisible by Y
        int divisibleByY = N / Y;
  
        // Count total number divisible by either X or Y
        int LCM = (X * Y) / gcd(X, Y);
        int divisibleByLCM = N / LCM;
        int divisibleByXorY = divisibleByX + divisibleByY
                              - divisibleByLCM;
  
        // Count total number divisible by X but not Y
        int divisibleByXnotY = divisibleByXorY 
                                          - divisibleByY;
  
        return divisibleByXnotY;
    }
  
    // Driver Code
    public static void main(String[] args)
    {
  
        int X = 2, Y = 3, N = 10;
        System.out.println(countNumbers(X, Y, N));
    }
}

Python3

# Python 3 implementation of above approach
from math import gcd
  
# Function to count total numbers divisible 
# by x but not y in range 1 to N
def countNumbers(X, Y, N):
      
    # Count total number divisible by X
    divisibleByX = int(N / X)
  
    # Count total number divisible by Y
    divisibleByY = int(N / Y)
  
    # Count total number divisible 
    # by either X or Y
    LCM = int((X * Y) / gcd(X, Y))
    divisibleByLCM = int(N / LCM)
    divisibleByXorY = (divisibleByX + 
                       divisibleByY - 
                       divisibleByLCM)
  
    # Count total numbers divisible by 
    # X but not Y
    divisibleByXnotY = (divisibleByXorY - 
                        divisibleByY)
  
    return divisibleByXnotY
  
# Driver Code
if __name__ == '__main__':
    X = 2
    Y = 3
    N = 10
    print(countNumbers(X, Y, N))
  
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of above approach
  
using System;
class GFG {
  
    // Function to calculate GCD
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
  
    // Function to count total numbers divisible by
    // x but not y in range 1 to N
    static int countNumbers(int X, int Y, int N)
    {
  
        // Count total number divisible by X
        int divisibleByX = N / X;
  
        // Count total number divisible by Y
        int divisibleByY = N / Y;
  
        // Count total number divisible by either X or Y
        int LCM = (X * Y) / gcd(X, Y);
        int divisibleByLCM = N / LCM;
        int divisibleByXorY = divisibleByX + divisibleByY 
                                        - divisibleByLCM;
  
        // Count total number divisible by X but not Y
        int divisibleByXnotY = divisibleByXorY 
                                          - divisibleByY;
  
        return divisibleByXnotY;
    }
  
    // Driver Code
    public static void Main()
    {
  
        int X = 2, Y = 3, N = 10;
        Console.WriteLine(countNumbers(X, Y, N));
    }
}

PHP

<?php
// PHP implementation of above approach
  
function __gcd($a, $b) 
{ 
  
    // Everything divides 0 
    if ($a == 0) 
        return $b; 
    if ($b == 0) 
        return $a; 
  
    // base case 
    if($a == $b) 
        return $a ; 
      
    // a is greater 
    if($a > $b) 
        return __gcd( $a - $b , $b ); 
  
    return __gcd( $a , $b - $a ); 
} 
  
// Function to count total numbers divisible 
// by x but not y in range 1 to N
function countNumbers($X, $Y, $N)
{
  
    // Count total number divisible by X
    $divisibleByX = $N / $X;
  
    // Count total number divisible by Y
    $divisibleByY = $N /$Y;
  
    // Count total number divisible by either X or Y
    $LCM = ($X * $Y) / __gcd($X, $Y);
    $divisibleByLCM = $N / $LCM;
    $divisibleByXorY = $divisibleByX + $divisibleByY - 
                                       $divisibleByLCM;
  
    // Count total numbers divisible by X but not Y
    $divisibleByXnotY = $divisibleByXorY - 
                        $divisibleByY;
  
    return ceil($divisibleByXnotY);
}
  
// Driver Code
$X = 2;
$Y = 3;
$N = 10;
echo countNumbers($X, $Y, $N);
  
// This is code contrubted by inder_verma
?>

Producción:

Complejidad de tiempo: O(1)

Publicación traducida automáticamente

Artículo escrito por ihritik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

PHP

C++

Java

Python3

C#

PHP

Deja una respuesta Cancelar la respuesta