Búsqueda

Visitas: 36776

Divisores y Divisibilidad

Divisores

Un número es divisor o factor propio de otro si el primero divide exactamente al segundo, es decir, si el resto de la división del segundo por el primero es exactamente cero. Por ejemplo, los divisores de 5 son 1 y 2, los de 12 son 1, 2, 3, 4, 6, 12.

Si d es un divisor de n, entonces n/d también lo es. La mitad de los divisores de n son menores o iguales a la raíz cuadrada de n, la otra mitad son de la forma n/d.

Ejemplo:
2 es un divisor de 6, por lo tanto 6/2 = 3 es también un divisor de 6.
Los primeros 3 divisores de 12 son 1, 2, 3 todos menores o iguales a la raiz cuadrada de 12, los últimos 3 son 4, 6 y 12.

Si un número N = ai * bj * ... *ck entonces N tiene (i+1) * (j+1) * ... * (k+1) divisores.

Los siguientes códigos permiten calcular el número de divisores y los divisores de un número, para esto se apoyan en el algoritmo de factorización comprimida mostrado en la sección factores primos.

1) Calcular el número de divisores de un número. Llamamos a la función de factorización y después usamos la formula N = ai * bj * ... *ck para calcular el número de factores.

// después de la llamada a la función factoriza, f indica el número
// de factores distintos del número y el arreglo veces indica cuantas
// veces se repite el i-ésimo factor
int numero_divisores(int n)
{
  int divisores = 1;

  factoriza(n);
  for (int i=0; i<f; i++)
    divisores *= veces[i]+1;
  return divisores;
}
 

2) Calcular los divisores de un número. Llamamos a la función de factorización y después usamos una función recursiva para calcular los divisores. Para calcular los divisores nos basamos en lo siguiente:
Dado que podemos expresar a un número de la forma ai * bj * ... *ck, podemos calcular los divisores haciendo que los cada uno de los exponentes (i, j, ..., k) barra todos sus posibles valores (0..i, 0..j, ..., 0..k). Ejemplo: 12 = 22 * 31, sus divisores son: 1 = 20 * 30, 2 = 21 * 30, 3 = 20 * 31, 4 = 22 * 30, 6 = 21 * 31, 12 = 22 * 31.

// en divisor se almacenan los divisores del numero
// d es el número de divisores del número
int divisor[100], d;

void calc_div(int val, int k, int n)
{
  if (k == n) {
    divisor[d++] = val;
    return;
  }
  int aux = 1;
  for (int i=0; i<=veces[k]; i++)
    c_div(val * aux, k+1, n),
    aux *= factor[k];
}

void divisores(int n)
{
  // despues de la llamada a la función factoriza, en factor
  // quedan los diferentes factores del número, veces nos indica
  // el número de veces que aparece el i-ésimo factor y f el
  // número de distintos factores
  factoriza(n);
  // d = número de divisores, llamamos a la función calc_div
  // para que calcule los divisores
  d = 0;
  calc_div(1, 0, f);
  // ordenamos lo divisores (no siempre necesario)
  sort(divisor, divisor+d)// incluir algorithm
}
 

Problemas relacionados en la UVA

294 - Divisors
547 - DDF, en la parte interna de la solución del problema

Divisibilidad

Las reglas de divisiblidad nos sirven para determinar si un número es divisible entre otro sin la necesidad de tener que realizar la división para saberlo.

En la siguiente tabla se muestran las principales reglas de divisibilidad.

3
Si la suma de los dígitos del número es divisible entre 3, entonces el número también lo es.
4
Si los dos últimos digitos son divisibles entre 4, el número también lo es.
5
Si el último digito es 5 o 0, el número es divisible entre 5.
6
Si el número es divisible entre 2 y 3, también es divisible entre 6.
7
Toma el último digito, duplicalo y restalo del resto del número, si el resultado es divisible entre 7 (incluyendo al 0), el número también lo es.
8
Si los últimos 3 digitos son divisibles por 8, el número también lo es.
9
Si la suma de los digitos es divisible entre 9, el número también lo es.
10
Si el número termina en 0, este es divisible entre 10.
11
Subtrae la suma de los digitos impares de la suma de los digitos pares, si la diferencia, incluyendo al 0, es divisible por 11, el número también lo es. Ejemplo: 10989, impares = 1+9+9 = 19, pares = 0 + 8 = 8, 19 - 8 = 11 por lo tanto 10989 es divisible entre 11.
12
Si el número es divisible entre 3 y 4, también es divisible entre 12.
13
Borra el último digito del número, entonces resta 9 veces el digito borrado del número restante. Si lo que queda es divisible entre 13, entonces el número original también lo es.

Otros números

A continuación se menciona un método que puede ser ocupado para encontrar otras formulas:

1 1 (mod 13)
10 -3 (mod 13) (esto es, 10 - -3 es divisible entre 13)
100 -4 (mod 13) (esto es, 100 - -4 es divisible entre 13)
1000 -1 (mod 13) (esto es, 1000 - -1 es divisible entre 13)
10000 3 (mod 13)
100000 4 (mod 13)
1000000 1 (mod 13)

Llamemos a las unidades a, a las decenas b, a las centenas c, ... y así sucesivamente:

a - 3*b - 4*c - d + 3*e + 4*f + g - ...
si este número es divisible entre 13, entonces el número original también.

Usando este método podemos generar reglas de divisibilidad para otros números primos. Para números compuestos, solo hay que la divisibilidad de los divisores.

Más información: http://www2.sunysuffolk.edu/wrightj/MA22/Num/DivRule.htm

Problemas relacionados en la UVA

10070 - Leap Year or Not Leap Year and ...