Los números primos. Teorema fundamental de la aritmética

Números primos

Decimos que un número entero p>1 es primo si sus únicos divisores positivos son 1 y p.

Algunas propiedades importantes sobre los números primos y compuestos:

  1. Si p es primo, p|x1.x2...xn ⇒ p|xi para algún i
  2. Teorema Fundamental de la Aritmética: Todo número natural mayor que 1 o bien es primo, o bien se puede descomponer como producto de números primos. Además esta descomposición es única -salvo el orden de los factores-.
  3. Si un número n es compuesto, se verifica que ha de tener un divisor primo menor o igual que su raíz cuadrada.
  4. Existen infinitos números primos

El método más antiguo y conocido de obtener todos los números primos menores que un entero dado n es la criba de Eratóstenes,Bio método inventado por el matemático griego del mismo nombre en el siglo III a.C. Consiste en disponer en una tabla todos los enteros entre 2 y n. Se empieza eliminando de la tabla todos los múltiplos de 2. En el siguiente paso se hace igual con los múltiplos de 3, luego con los múltiplos de 5 (pues el 4 y sus múltiplos quedaron elimimados en el primer paso), etc. Así hasta que no puedan eliminarse más múltiplos de la tabla. Los números que finalmente queden en la tabla serán todos números primos, entre 2 y n.

Por la observación hecha anteriormente sobre los números compuestos, ocurre que sólamente es necesario cribar en la tabla hasta que lleguemos al paso correspondiente a un número mayor o igual que √n. El resto de números que queden por tachar a partir de este momento ya serán todos números primos.

Correr aplicación Aplicación de ejemplo: La criba de Eratóstenes


Anterior Arriba Siguiente