Tema 3
Divisibilidad, módulo y números primos
Patrón de examen
Usa criba cuando necesites múltiples consultas de primalidad. Para una sola verificación, usa O(√n). Combina criba + suma de prefijos para contar primos en rangos.
Explicación
Módulo (residuo de la división)
En C++: a % b da el residuo de dividir a entre b.
Propiedades esenciales
(a + b) % m = ((a % m) + (b % m)) % m(a * b) % m = ((a % m) * (b % m)) % ma % m == 0→ m divide a a
Aplicaciones comunes
- Par/impar:
n % 2 == 0 - Múltiplos:
n % k == 0 - Evitar overflow: calcular
(a + b) % MODen todo momento
Números primos
Divisible solo por 1 y por sí mismo.
Verificación O(√n)
Probar divisores de 2 hasta √n.
Criba de Eratóstenes O(n log log n)
Genera todos los primos hasta N. Esencial para múltiples consultas de primalidad.