como saber si un numero es primo o no. teorema de euclides

Se dice que un número es primo cuando sus únicos divisores son él mismo y la unidad. Por ejemplo 5, 7 y 23 son primos. El número 18, en cambio, es compuesto, ya que tiene más divisores (1, 2, 3, 6, 9 y 18).

Se puede hacer una lista de números primos con la llamada Criba de Eratóstenes, que consiste en tachar todos los múltiplos de 2 (ya que serán compuestos al ser el 2 un divisor). Después tachamos todos los múltiplos de 3 (por lo mismo). El 4 estará tachado, así que lo saltamos. El 5 está sin tachar, así que tachamos todos los múltiplos de 5. Continuamos este proceso, tachando los múltiplos de los números que no estén tachados. Los números que "sobreviven" a esta criba son los números primos. Los primeros son:


2 3 5 7 11 13 17 19 23 29 ...

Para saber si un número es primo, lo vamos dividiendo por 2, 3, 5... hasta que encontremos una división exacta, en cuyo caso el número sería compuesto, o bien hasta que el cociente de la división sea menor que el divisor. Si hemos llegado a este punto sin encontrar ninguna división exacta, el número dado es primo.
Ejemplos: El numero 49: Dividimos por 2 y no es exacta. Dividimos por 3 y tampoco. Por 5 tampoco. Por 7 sí es exacta, luego el número 49 no es primo, es divisible por 7.
El numero 53: Dividimos por 2 y no es exacta, Por 3 tampoco, ni por 5 ni por 7. Dividimos entre 11 y tampoco es exacta, pero hemos llegado a que el cociente, 4, es menor que el divisor, 11, por lo que el número 53 es primo.



Algoritmo original de Euclides
AB y CD son segmentos conmensurables.
Ejemplo del algoritmo original de Euclides.En la concepción griega de la matemática, los números se entendían como magnitudes geométricas. Un tema recurrente en la geometría griega es el de la conmensurabilidad de dos segmentos: dos segmentos (números) AB y CD son conmensurables cuando existe un tercer segmento PQ el cual cabe exactamente un número entero de veces en los primeros dos, es decir, PQ «mide» (mensura: medida) a los segmentos AB y CD.

No cualquier par de segmentos es conmensurable, como encontraron los pitagóricos cuando establecen que el lado y la diagonal de un cuadrado no son conmensurables, pero en el caso de dos segmentos conmensurables se desea hallar la mayor medida común posible.

Euclides describe en la proposición VII.2 de sus Elementos un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.

Para encontrar la máxima medida común de dos números que no sean primos entre sí.
Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.

Si CD mide AB entonces es una medida común puesto que CD se mide a sí mismo. Y es manifiesto que también es la mayor medida pues nada mayor a CD puede medir a CD. Pero si CD no mide a AB entonces algún número quedará de AB y CD, el menor siendo continuamente restado del mayor y que medirá al número que le precede. Porque una unidad no quedará pues si no es así, AB y CD serán primos uno del otro [Prop. VII.1], lo cual es lo contrario de lo que se supuso.

Por tanto, algún número queda que medirá el número que le precede. Y sea CD midiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FC menor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mide DF, FC será entonces medida de DF. Y también se mide a sí mismo. Por tanto también medirá todo CD. Y CD mide a BE. Entonces CF mide a BE y también mide a EA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por lo que es una medida común de AB y CD.

Afirmo que también es la mayor medida común posible porque si no lo fuera, entonces un número mayor que CF mide a los números AB y CD, sea éste G. Dado que G mide a CD y CD mide a BE, G también mide a BE. Además, mide a todo BA por lo que mide también al residuo AE. Y AE mide a DF por lo que G también mide a DF. Mide también a todo DC por lo que mide también al residuo CF, es decir el mayor mide al menor, lo cual es imposible.

Por tanto, ningún número mayor a CF puede medir a los números AB y CD. Entonces CF es la mayor medida común de AB y CD, lo cual se quería demostrar.

Euclides. Elementos VII.2
En lenguaje moderno, el algoritmo se describe como sigue:

1.Dados dos segmentos AB y CD (con AB>CD), restamos CD de AB tantas veces como sea posible. Si no hay residuo, entonces CD es la máxima medida común.
2.Si se obtiene un residuo EF, éste es menor que CD y podemos repetir el proceso: restamos EF tantas veces como sea posible de CD. Si al final no queda un residuo, EF es la medida común. En caso contrario obtenemos un nuevo residuo GH menor a EF.
3.El proceso se repite hasta que en algún momento no se obtiene residuo. Entonces el último residuo obtenido es la mayor medida común.
El hecho de que los segmentos son conmesurables es clave para asegurar que el proceso termina tarde o temprano

Algoritmo de Euclides tradicionalAl dividir a entre b (números enteros), se obtiene un cociente q y un residuo r. Es posible demostrar que el máximo común divisor de a y b es el mismo que el de b y r. Éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número a y 0 es precisamente a. Para fines prácticos, la notación mcd(a,b) significa máximo común divisor de a y b.

Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

Algoritmo Un algoritmo es un método para resolver un problema, debe presentarse como una secuencia ordenada de instrucciones que siempre se ejecutan en un tiempo finito y con una cantidad de esfuerzo también finito. En un algoritmo siempre debe haber un punto de inicio y un punto de terminación, estos deben ser únicos y deben ser fácilmente identificables. CARACTERÍSTICAS DE UN ALGORITMO Todo algoritmo debe cumplir las siguientes características: Debe ser Preciso; Esto es, debe especificar sin ambigüedad el orden en que se deben ejecutar las instrucciones. Debe estar Definido; Esto es, cada vez que se ejecute bajo las mismas condiciones, la secuencia de ejecución deberá ser la misma proporcionándonos el mismo resultado. Debe ser Finito; Esto es, siempre que sea adecuado se realizarán un número finito de instrucciones, en un tiempo finito y requiriendo una cantidad finita de esfuerzo. REPRESENTACIÓN DE ALGORITMOS Existen varias maneras de representar algoritmos, una de las más evidentes es el lenguaje natural; sin embargo el lenguaje natural no siempre es lo suficientemente preciso. Como alternativa tenemos el Pseudocódigo. Pseudocódigo El pseudocódigo es un forma de representar un algoritmo, mediante sentencias similares al lenguaje natural, pero con una precisión mayor. Existen muchas variantes de pseudocódigo, aquí se adoptarán las siguientes normas: Todos los algoritmos comenzarán con una sentencia algoritmo, Esto es, una línea con la palabra clave algoritmo seguida por el nombre del algoritmo. Por ejemplo: Algoritmo EJEMPLO Después de la sentencia algoritmo se declararán las constantes que se requieran en el programa. La decisión de constantes se identificará con la palabra clave constantes. Por ejemplo: Constante PI 3.1416 Constante UNO 1 A continuación aparecerá el desarrollo del algoritmo, al cual nombraremos PRINCIPAL. Dicho desarrollo se encontrará entre las palabras clave inicio y fin. Estas palabras clave limitarán un bloque de instrucciones siempre que se requieran. Por ejemplo: PRINCIPAL Inicio ..... Fin A continuación de la palabra clave inicio se declaran las variables. En este caso el tipo de variables se indicará al principio de la lista; separada por un espacio se colocará la lista de variables, separadas por comas (,). Cada lista incluirá solamente variables de mismo tipo. Ejemplo: Flotante X, Y, Z Enteras I, J, K En cualquier parte del algoritmo podrán colocarse comentarios para hacer aclaraciones o comentarios relacionados con la instrucción u operación que faciliten la interpretación. Los comentarios aparecerán encerrados entre /*y*/. Ejemplo: /* Este es un comentario*/ Las palabras clave se imprimirán en letra negrita. Cuando se use letra manuscrita se sugiere subrayar las palabras clave.