{"id":1261,"date":"2014-03-14T08:25:44","date_gmt":"2014-03-14T13:25:44","guid":{"rendered":"http:\/\/blog.espol.edu.ec\/icm00794\/?p=1261"},"modified":"2026-04-05T17:13:49","modified_gmt":"2026-04-05T22:13:49","slug":"s1eva2008ti_t2-criba-de-eratostenes","status":"publish","type":"post","link":"https:\/\/blog.espol.edu.ec\/algoritmos101\/fp-s1eva10\/s1eva2008ti_t2-criba-de-eratostenes\/","title":{"rendered":"s1Eva2008TI_T2 Criba de Erat\u00f3stenes con Python"},"content":{"rendered":"\n

Ejercicio<\/strong><\/em>: 1Eva2008TI_T2 Criba de Erat\u00f3stenes<\/a><\/p>\n\n\n\n

\n\n\n\n
\n

algoritmo<\/a><\/p>\n\n\n\n

diagrama flujo<\/a><\/p>\n<\/div>\n\n\n\n

\n\n\n\n

- Se forma un vector con todos los n\u00fameros naturales<\/strong> entre 2<\/strong> y n<\/strong>.<\/p>\n\n\n\n

i<\/td>2<\/td>3<\/td>4<\/td>5<\/td>6<\/td>7<\/td>8<\/td>9<\/td>10<\/td>11<\/td>12<\/td>13<\/td>14<\/td>15<\/td>16<\/td>17<\/td>18<\/td>19<\/td>20<\/td><\/tr>
criba[i]<\/td>1<\/td>1<\/td>0<\/td>1<\/td>0<\/td>1<\/td>0<\/td>0<\/td>0<\/td>1<\/td>0<\/td>1<\/td>0<\/td>0<\/td>0<\/td>1<\/td>0<\/td>1<\/td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Llenar un arreglo de marcas o tachado con la hip\u00f3tesis que todos son primos(1).<\/p>\n\n\n\n

# PROCEDIMIENTO<\/span>\nmarcado = np.zeros((n+1),dtype=int<\/span>)\n# hipotesis: todos son primos<\/span>\ncriba = 2\nwhile<\/span> (criba<=n):\n    marcado[criba] = 1\n    criba = criba+1<\/code><\/pre>\n\n\n\n
La prueba de hip\u00f3tesis consiste en usar un indicador para el n\u00famero de criba<\/strong><\/em>, y otro indicador i<\/em><\/strong> para anular marcando con cero (0) las posiciones de los m\u00faltiplos.<\/p>\n\n\n\n
- Se tachan todos los m\u00faltiplos de 2 <\/strong>que son menores que n<\/strong>,<\/p>\n\n\n\n
Inicie eliminando los m\u00faltiplos de 2, para luego cambiar a los m\u00faltiplos de 3, etc.<\/p>\n\n\n\n
# no son primos los m\u00faltiplos <\/span>\ncriba = 2<\/strong>\nwhile<\/span> (criba<=n):\n\n    # revisa el primer m\u00faltiplo<\/span>\n    i<\/strong> = criba * 2<\/strong>\n    while<\/span> (i<\/strong><=n):\n        marcado[i] = 0<\/strong>\n        i = i + criba\n    criba = criba+1<\/code><\/pre>\n\n\n\n
Mostrar como resultado solo aquellos n\u00fameros mantienen en marcas v\u00e1lidas (1<\/strong>).<\/p>\n\n\n\n
Tarea<\/strong><\/em>: Analizar si es necesario hacer funcionar el algoritmo de la prueba de hip\u00f3tesis hasta n<\/strong> o un n\u00famero menor. Realizar la validaci\u00f3n que n<\/strong> sea mayor que 1.<\/p>\n\n\n\n
\n\n\n\n
\n
algoritmo<\/a><\/p>\n\n\n\n
diagrama flujo<\/a><\/p>\n<\/div>\n\n\n\n
\n\n\n\n
Algoritmo en Python<\/h2>\n\n\n
\n# ICM00794-Fundamentos de Computaci\u00f3n - FCNM-ESPOL\n# 1Eva_IT2008_T2 Criba de Erat\u00f3stenes\n# Propuesta: edelros@espol.edu.ec\n\nimport numpy as np\n\n# INGRESO\nn = int(input('primos menores que: '))\n\n# PROCEDIMIENTO\nmarcado = np.zeros((n+1),dtype=int)\n\n# hipotesis: todos son primos\ncriba = 2\nwhile (criba<=n):\n    marcado[criba] = 1\n    criba = criba+1\n\n# no son primos los m\u00faltiplos \ncriba = 2\nwhile (criba<=n):\n\n    # revisa el primer m\u00faltiplo\n    i = criba * 2\n    while (i<=n):\n        marcado[i] = 0\n        i = i + criba\n    criba = criba+1\n\n# SALIDA\ncriba = 2\nwhile (criba<=n):\n    if marcado[criba]==1:\n        print(criba)\n    criba = criba+1\n\n<\/pre><\/div>\n\n\n
resultado del algoritmo<\/p>\n\n\n\n
primos menores que: 30\n2\n3\n5\n7\n11\n13\n17\n19\n23\n29\n>>> <\/code><\/pre>\n\n\n\n
\n\n\n\n
\n
algoritmo<\/a><\/p>\n\n\n\n
diagrama flujo<\/a><\/p>\n<\/div>\n\n\n\n
\n\n\n\n
Diagrama de Flujo<\/h2>\n\n\n\n
\"diagrama<\/figure>\n\n\n\n
<\/p>\n\n\n\n
\"diagrama<\/figure>\n\n\n\n
<\/p>\n\n\n\n
\"diagrama<\/figure>\n\n\n\n
<\/p>\n\n\n\n
\n\n\n\n
\n
algoritmo<\/a><\/p>\n\n\n\n
diagrama flujo<\/a><\/p>\n<\/div>\n\n\n\n
\n\n\n\n
Otra forma de plantear el algoritmo<\/p>\n\n\n
\n# 1ra Evaluaci\u00f3n I T\u00e9rmino 2008\n# Tema 2. Criba de Erat\u00f3stenes\nimport numpy as np\n\n# INGRESO\nn = int(input('cuantos numeros analiza: '))\n\n# PROCEDIMIENTO\n# vector de n\u00fameros naturales\nnatural = np.zeros(n, dtype=int)\nposicion =  0\nwhile not(posicion>=n):\n    natural[posicion] = posicion\n    posicion = posicion +1\n\n# hipotesis todos cumplen\ncumple = np.ones(n,dtype = int)\n\n# Tarea: analiza cada posici\u00f3n\nposicion = 2\n# elimina multiplos \/ no cumplen\ncontador = 2\ntacha  = posicion *contador\nwhile not(tacha>(n-1)):\n    tacha  = posicion *contador\n    if tacha<(n-1):\n        cumple[tacha] = 0\n    contador = contador +1\n\n# SALIDA\n# solo valores de la posicion 2 en adelante\nprint(natural[2:])\nprint(cumple[2:])\n<\/pre><\/div>\n\n\n
mostrando el siguiente resultado:<\/p>\n\n\n\n
cuantos numeros analiza: 50\n[ 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19\n 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37\n 38 39 40 41 42 43 44 45 46 47 48 49]\n[1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0\n 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]\n>>> <\/code><\/pre>\n\n\n\n
\n\n\n\n
\n
algoritmo<\/a><\/p>\n\n\n\n
diagrama flujo<\/a><\/p>\n<\/div>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"
Ejercicio: 1Eva2008TI_T2 Criba de Erat\u00f3stenes algoritmo diagrama flujo - Se forma un vector con todos los n\u00fameros naturales entre 2 y n. i 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 criba[i] 1 1 0 1 0 1 0 0 0 1 0 1 […]<\/p>\n","protected":false},"author":8043,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"wp-custom-template-entrada-fp-ejemplos","format":"standard","meta":{"footnotes":""},"categories":[125],"tags":[58,157],"class_list":["post-1261","post","type-post","status-publish","format-standard","hentry","category-fp-s1eva10","tag-ejemplos-python","tag-fundamentos-programacion"],"_links":{"self":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/1261","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/users\/8043"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/comments?post=1261"}],"version-history":[{"count":4,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/1261\/revisions"}],"predecessor-version":[{"id":23565,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/1261\/revisions\/23565"}],"wp:attachment":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/media?parent=1261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/categories?post=1261"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/tags?post=1261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}