Page 73 - 16 Fermat

LA CRIBA DE ERATÓSTENES Y LA COMPLEJIDAD

La criba de Eratóstenes es el método más antiguo para determinar si un nú-
mero N es primo. Para ello, se hace una lista de todos los números hasta N.
Partiendo del primer primo, el 2, se tachan de esa lista todos los múltiplos de
2 hasta N. Luego se hace lo propio para el primer número no tachado de la
lista, que es el 3, luego el 5, etc., hasta llegar al número más cercano a ✓N.
Cada primer número no tachado es primo. Si en cualquier momento de este
proceso se tacha N, sabemos que N es un número compuesto. Por el contra-
rio, si se llega al último número, el primo más cercano a ✓N, N es primo. Evi-
dentemente, el método es engorroso, ya que requiere conocer todos los nú-
N
meros primos hasta ✓. Un método similar es la división por tentativa. En este
caso, se divide por todos los primos hasta ✓N (obtenidos previamente), o bien
N
por dos y todos los impares hasta ✓, hasta encontrar uno que divida a N o
agotar la lista.
Eficiencia computacional
Los métodos como la criba de Eratóstenes claramente pueden ser más o
menos eficientes. El estudio de la eficiencia computacional de un algoritmo
es una de las ramas de investigación más importantes en computación. Hay
problemas que son irresolubles, dado que no existe un algoritmo que pueda
dar siempre una respuesta. De los problemas que son solubles, podemos
est imar cuál es el tiempo máximo en el que se resüelve el problema con un
algoritmo dado. Esto se representa como O(f(n)), donde f(n) es cualquier
función de n, que a su vez es una medida del «tamaño» del problema (por
ejemplo, puede ser el número de elementos de una lista). Puede haber algo-
2
ritmos con complej idad: O(n), O(n ),0(log n),O(n log n),O(e n), etc. Por otro
lado, existen problemas que, siendo solubles, requieren tanto tiempo que no
es realista intentar resolverlos. Son los problemas de complej idad exponen-
cial: O(e n) o, peor aún, combinatoria: O(n!), por ejemplo, contar todas las
permutaciones den objetos. Reciben el nombre de problemas intratables.
Hay otra clase de problemas muy interesante: aquellos que podrían ser intra-
tables, pero no sabemos si lo son. Conceptualmente, son problemas en los
que, si se conoce la solución, es m uy fácil comprobar si dicha solución es
verdadera, pero en los que encontrar la solución, al parecer es un problema
intratable. Decimos «al parecer» porque nadie ha podido demostrar si lo son.
Estos problemas se llaman problemas NP. El problema de factorizar un nú-
mero es el ejemplo más relevante para nosotros. Finalmente, existen los pro-
b lemas tratables, que son los que sabemos que son solubles en un tiempo
razonable, del orden de O(nk), O(n logn) u O(logn), conocidos como tiempos
polinomiales. La criba de Eratóstenes es un algorit mo con complej idad
0(10,r,; ), claramente exponencial.

LA MODERNA TEORÍA DE NÚMEROS 73