Matemáticas/Aritmética/Números Primos

Introducción.

En el siglo III a.c. Eratótenes ideó la primera tabla para saber si un número es primo o compuesto.
Se denomina Criba por el original método que siguió para construirla; escribió en una lámina metálica los primeros cuatro mil números naturales, y luego hizo agujeros sobre los que eran múltiplos de 2, 3, etc. eliminando de esta manera los números compuestos. Los números que quedaban sin agujerear resultaban ser los primos.
La lámina al final de la tarea presenta muchos agujeros por lo que parece un colador o criba, de ahí su nombre.

Criba de Eratóstenes

Algoritmo que permite hallar todos los números primos menores que un número natural dado N.
Se forma una tabla con todos los números tachando los números que son primos de la siguiente manera.
Se forma una tabla con todos los números naturales desde 2 hasta N.

${\begin{array}{cccccccccc}&&2&3&4&5&6&7&8&9\\10&11&12&13&14&15&16&17&18&19\\20&21&22&23&24&25&26&27&28&29\\30&31&32&33&34&35&36&37&38&39\\40&41&42&43&44&45&46&47&48&49\\50&51&52&53&54&55&56&57&58&59\\60&61&62&63&64&65&66&67&68&69\\70&71&72&73&74&75&76&77&78&79\\80&81&82&83&84&85&86&87&88&89\\90&91&92&93&94&95&96&97&98&99\\\end{array}}$

Comenzando con el 2, y tachando todos sus múltiplos siguientes. Cada vez que se encuentre un número entero que no ha sido tachado, se señala como primo y se procede a tachar todos sus múltiplos siguientes. El proceso termina cuando del cuadrado del mayor número confirmado como primo supera a N.

${\begin{array}{cccccccccc}&&2&3&{\cancel {4}}&5&{\cancel {6}}&7&{\cancel {8}}&{\cancel {9}}\\{\cancel {10}}&11&{\cancel {12}}&13&{\cancel {14}}&{\cancel {15}}&{\cancel {16}}&17&{\cancel {18}}&19\\{\cancel {20}}&{\cancel {21}}&{\cancel {22}}&23&{\cancel {24}}&{\cancel {25}}&{\cancel {26}}&{\cancel {27}}&{\cancel {28}}&29\\{\cancel {30}}&31&{\cancel {32}}&{\cancel {33}}&{\cancel {34}}&{\cancel {35}}&{\cancel {36}}&37&{\cancel {38}}&{\cancel {39}}\\{\cancel {40}}&41&{\cancel {42}}&43&{\cancel {44}}&{\cancel {45}}&{\cancel {46}}&47&{\cancel {48}}&{\cancel {49}}\\{\cancel {50}}&{\cancel {51}}&{\cancel {52}}&53&{\cancel {54}}&{\cancel {55}}&{\cancel {56}}&{\cancel {57}}&{\cancel {58}}&59\\{\cancel {60}}&61&{\cancel {62}}&{\cancel {63}}&{\cancel {64}}&{\cancel {65}}&{\cancel {66}}&67&{\cancel {68}}&{\cancel {69}}\\{\cancel {70}}&71&{\cancel {72}}&73&{\cancel {74}}&{\cancel {75}}&{\cancel {76}}&{\cancel {77}}&{\cancel {78}}&79\\{\cancel {80}}&{\cancel {81}}&{\cancel {82}}&83&{\cancel {84}}&{\cancel {85}}&{\cancel {86}}&{\cancel {87}}&{\cancel {88}}&89\\{\cancel {90}}&{\cancel {91}}&{\cancel {92}}&{\cancel {93}}&{\cancel {94}}&{\cancel {95}}&{\cancel {96}}&97&{\cancel {98}}&{\cancel {99}}\end{array}}$

Los números primos menores de 100 son:

$\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\}$

El número uno: (1), no se considera primo.