El cribado de Erat\u00f3stenes es un algoritmo para averiguar todos los n\u00fameros primos menores que un n\u00famero natural dado. Los n\u00fameros naturales, a diferencia de los enteros, no comprenden los n\u00fameros negativos.<\/p>\n\n\n\n
Se considera un n\u00famero primo el n\u00famero que tiene dos divisores, el propio n\u00famero y 1, por tanto, dado que el n\u00famero 1 s\u00f3lo tiene un divisor, el primer n\u00famero primo es el 2.<\/p>\n\n\n\n
Con la criba de Erat\u00f3stenes se crea una tabla de n\u00fameros desde el 2 hasta el n\u00famero natural dado y comenzando por el 2, se tachan todos sus m\u00faltiplos, el siguiente n\u00famero no tachado es un n\u00famero primo y se tachan todos sus m\u00faltiplos, as\u00ed sucesivamente hasta que el cuadrado del siguiente n\u00famero sea mayor que el n\u00famero dado.<\/p>\n\n\n\n
\u00bfC\u00f3mo hacemos esto con Python?<\/p>\n\n\n\n
Podemos crear una funci\u00f3n y llamarla cribado_eratostenes(n)<\/strong> , esta contendr\u00e1 \u00e9l algoritmo. Este ha de comenzar declarando dos variables, una para sumar la cantidad de n\u00fameros primos encontrados y otra donde almacenar\u00e1 una lista de n\u00fameros del 2 hasta el n\u00famero n dado.<\/p>\n\n\n\n Para continuar recorremos los n\u00fameros de la lista verificando que no sea None (tachado), si lo fuera continua con el siguiente, si el siguiente es un n\u00famero diferente de None (no tachado) es por tanto primo, as\u00ed que convierte en None (tacha) los m\u00faltiplos del n\u00famero, hasta el n\u00famero final dado.<\/p>\n\n\n\n Finalmente devuelve el total y una lista con los n\u00fameros restantes diferentes a None, es decir los n\u00fameros primos que son los no tachados.<\/p>\n\n\n\n Vamos a usar el algoritmo para averiguar los n\u00fameros primos entre 2 y 20, para eso usamos la funci\u00f3n: cribado_eratostenes(20) <\/strong>obteniendo dos valores el total de n\u00fameros primos y la lista de n\u00fameros primos como en el ejemplo:<\/p>\n\n\n\n \u00bfY si le dec\u00eds que averig\u00fce algunos n\u00fameros primos mas?<\/p>\n","protected":false},"excerpt":{"rendered":" El cribado de Erat\u00f3stenes es un algoritmo para averiguar todos los n\u00fameros primos menores que un n\u00famero natural dado. Los … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-353","post","type-post","status-publish","format-standard","hentry","category-python"],"_links":{"self":[{"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/posts\/353","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=353"}],"version-history":[{"count":5,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions"}],"predecessor-version":[{"id":358,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions\/358"}],"wp:attachment":[{"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pythonparatodo.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}def cribado_eratostenes(n):\n \"\"\"\n Implementaci\u00f3n del Cribado de Erat\u00f3stenes\n \"\"\"\n total=0\n # Creamos una lista con todos los n\u00fameros del 2 al n\n numeros = list(range(2, n+1))\n # Iniciamos el cribado\n for i in numeros:\n # Si el n\u00famero ya ha sido marcado como no primo, saltamos a la siguiente iteraci\u00f3n\n if i is None:\n continue\n # Si el n\u00famero es primo, marcamos todos sus m\u00faltiplos como no primos\n total+=1\n for j in range(i*2, n+1, i):\n numeros[j-2] = None\n # Devolvemos una lista con los n\u00fameros primos encontrados\n return total,[num for num in numeros if num is not None]\n\n# Encontramos los primeros n\u00fameros primos\ntotal,primos = cribado_eratostenes(20)\n# Imprimimos los resultados\nprint(f\"Total de n\u00fameros encontrados {total}, n\u00fameros primos {primos}\")<\/code><\/pre>\n\n\n\nTotal de n\u00fameros encontrados 8, n\u00fameros primos [2, 3, 5, 7, 11, 13, 17, 19]<\/code><\/pre>\n\n\n\n