Comprueba si algún número grande es divisible por 17 o no

Dado un número, la tarea es verificar rápidamente si el número es divisible por 17 o no.
Ejemplo:

Input : x = 34
Output : Yes

Input : x = 47
Output : No

Una solución al problema es extraer el último dígito y restar 5 veces el último dígito del número restante y repetir este proceso hasta obtener un número de dos dígitos. Si el número de dos dígitos obtenido es divisible por 17, entonces el número dado es divisible por 17.
Enfoque:

Extraiga el último dígito del número/número truncado cada vez
Resta 5*(último dígito del número anterior) del número truncado
Repita los tres pasos anteriores todo el tiempo que sea necesario.

Ilustración:

3978-->397-5*8=357-->35-5*7=0. 
So 3978 is divisible by 17.

Prueba matemática:
Sea $\overline{a b c}$ cualquier número tal que $\overline{a b c}$ =100a+10b+c.
Ahora suponga que $\overline{a b c}$ es divisible por 17. Entonces
$\overline{a b c}\equiv$ 0 (mod 17)
100a+10b+c $\equiv$ 0 (mod 17)
10(10a+b)+c $\equiv$ 0 (mod 17)
10 $\overline{a b}$ +c $\equiv$ 0 (mod 17)
Ahora que hemos separado el último dígito del número, tenemos que encontrar una manera de usarlo.
Haz el coeficiente de $\overline{a b}$ 1.
En otras palabras, tenemos que encontrar un entero tal que n tal que 10n $\equiv$ 1 mod 17.
Se puede observar que el n más pequeño que satisface esta propiedad es -5 como -50 $\equiv$ 1 mod 17.
Ahora puede multiplicar la ecuación original 10 $\overline{a b}$ +c $\equiv$ 0 (mod 17)
por -5 y simplificarlo:
-50 $\overline{a b}$ -5c $\equiv$ 0 (mod 17)
$\overline{a b}$ -5c $\equiv$ 0 (mod 17)
Hemos encontrado que si $\overline{a b c}\equiv$ 0 (mod 17) entonces,
$\overline{a b}$ -5c $\equiv$ 0 (mod 17).
En otras palabras, para verificar si un número de 3 dígitos es divisible por 17,
podemos quitar el último dígito, multiplicarlo por 5
y luego restarlo del resto de los dos dígitos.

Programa :

C++

// CPP Program to validate the above logic
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to check if the
// number is divisible by 17 or not
bool isDivisible(long long int n)
{
 
    while (n / 100)
    {
        // Extracting the last digit
        int d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the five times the
        // last digit from the remaining number
        n -= d * 5;
    }
 
    // Return n is divisible by 17
    return (n % 17 == 0);
}
 
// Driver code
int main()
{
    long long int n = 19877658;
    if (isDivisible(n))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Java

// Java Program to validate the above logic
 
import java.io.*;
 
class GFG {
 
 
// Function to check if the
// number is divisible by 17 or not
 static boolean isDivisible(long n)
{
 
    while (n / 100>0)
    {
        // Extracting the last digit
        long d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the five times the
        // last digit from the remaining number
        n -= d * 5;
    }
 
    // Return n is divisible by 17
    return (n % 17 == 0);
}
 
// Driver code
 
    public static void main (String[] args) {
    long n = 19877658;
    if (isDivisible(n))
        System.out.println( "Yes");
    else
        System.out.println( "No");
    }
}
// This code is contributed by inder_verma.

Python 3

# Python 3 Program to validate
# the above logic
 
# Function to check if the
# number is divisible by 17 or not
def isDivisible(n) :
 
    while(n // 100) :
 
        # Extracting the last digit
        d = n % 10
 
        # Truncating the number
        n //= 10
 
        # Subtracting the five times 
        # the last digit from the
        # remaining number
        n -= d * 5
 
    # Return n is divisible by 17
    return (n % 17 == 0)
 
# Driver Code
if __name__ == "__main__" :
 
    n = 19877658
     
    if isDivisible(n) :
        print("Yes")
    else :
        print("No")
 
# This code is contributed
# by ANKITRAI1

C#

// C# Program to validate the above logic
  
using System;
  
class GFG {
  
  
// Function to check if the
// number is divisible by 17 or not
 static bool isDivisible(long n)
{
  
    while (n / 100>0)
    {
        // Extracting the last digit
        long d = n % 10;
  
        // Truncating the number
        n /= 10;
  
        // Subtracting the five times the
        // last digit from the remaining number
        n -= d * 5;
    }
  
    // Return n is divisible by 17
    return (n % 17 == 0);
}
  
// Driver code
  
    public static void Main () {
    long n = 19877658;
    if (isDivisible(n))
        Console.Write( "Yes");
    else
        Console.Write( "No");
    }
}

PHP

<?php
// PHP Program to validate the above logic
 
// Function to check if the
// number is divisible by 17 or not
function isDivisible($n)
{
 
    while ($n / 100 != 0)
    {
        // Extracting the last digit
        $d = (int)$n % 10;
 
        // Truncating the number
        $n /= 10;
 
        // Subtracting the five times
        // the last digit from the
        // remaining number
        $n -= $d * 5;
    }
 
    // Return n is divisible by 17
    return ($n % 17 == 0);
}
 
// Driver code
$n = 19877658;
if (isDivisible($n))
    print("Yes");
else
    print("No");
 
// This code is contributed by Raj
?>

Javascript

<script>
 
// JavaScript Program to validate the above logic
     
    // Function to check if the
// number is divisible by 17 or not
    function isDivisible(n)
    {
        while (Math.floor(n / 100)>0)
    {
        // Extracting the last digit
        let d = n % 10;
   
        // Truncating the number
        n = Math.floor(n/10);
   
        // Subtracting the five times the
        // last digit from the remaining number
        n -= d * 5;
    }
   
    // Return n is divisible by 17
    return (n % 17 == 0);
    }
     
    // Driver code
    let n = 19877658;
    if (isDivisible(n))
        document.write( "Yes");
    else
        document.write( "No");
         
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción:

Yes

Complejidad de tiempo: O(log ₁₀ n), tiempo requerido para verificar si el número es divisible por 17
Espacio auxiliar: O(1), ya que no se requiere espacio adicional

Tenga en cuenta que el programa anterior puede no tener mucho sentido, ya que simplemente podría hacer n % 23 para verificar la divisibilidad. La idea de este programa es validar el concepto. Además, este podría ser un enfoque eficiente si el número de entrada es grande y se proporciona como una string.

Publicación traducida automáticamente

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

C++

Java

Python 3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta