Discusión:La criba de Eratóstenes

Punto de referencia

Según recuerdo, la criba de Eratóstenes era un punto de referencia popular para los primeros microordenadores. Pensé que podría encontrar un comentario al respecto aquí (bueno, es posible). Parece que no es así. Quería hacer referencia a ella desde la página de MIPS. Gah4 ( discusión ) 09:02 13 ago 2016 (UTC) [ responder ]

Se usaba comúnmente como punto de referencia. Bubba73 ¿ ^{Me estás hablando a mí?} 15:57, 13 de agosto de 2016 (UTC) [ responder ]

Diseño visual

Si bien se mejoró mucho en varios aspectos del estilo tipográfico (¡gracias por eso!), una edición reciente realizada por un usuario de IP 81.129.155.32 también destruyó el diseño visual cuidadosamente creado de fragmentos de pseudocódigo y ejemplos en todo el artículo.

Por favor, no lo hagas sin discutirlo aquí y llegar a un consenso primero. Gracias. WillNess ( discusión ) 10:12 24 ene 2017 (UTC) [ responder ]

(Deshaga la edición de buena fe que no pertenece a esta subsección. La complejidad ya se analiza en otra parte del artículo. La mención pasajera de otro algoritmo incremental es suficiente, no es necesario _su_ análisis profundo).

Un artículo de revisión reciente tiene lo anterior como resumen de edición. Si bien esto puede ser cierto, es desalentador para los nuevos editores. Si hay demasiados, alguien dejará de intentarlo. ¿Es posible poner algo más en el artículo? ¿O cambiarlo de manera que sea un agregado útil? Parece que alguien realmente entiende el tema, no una edición aleatoria e inapropiada. Gah4 ( discusión ) 20:44, 6 de abril de 2017 (UTC) [ responder ]

Animación inconsistente: no marca 6 en verde al marcar múltiplos de 3

Cuando la animación marca múltiplos de 3 en verde, no marca el número 6 en verde. Se podría argumentar que esto se debe a que el 6 ya está marcado en rojo como múltiplo de 2. Pero la animación luego marca otros múltiplos de 3 en verde incluso cuando ya se han marcado en rojo como múltiplos de 2 (por ejemplo, 18, 48, 54, 96). Parece que la animación debería marcar el 6 en verde cuando marca múltiplos de 3. — Comentario anterior sin firmar agregado por 62.190.148.115 ( discusión ) 18:24, 18 de septiembre de 2017 (UTC) [ responder ]

El título dice "incluyendo la optimización a partir del cuadrado de Prime". Eso significa que los múltiplos de 2 se marcan a partir de 2 ² = 4 (lo cual no hace ninguna diferencia), los múltiplos de 3 se marcan a partir de 3 ² = 9, los múltiplos de 5 se marcan a partir de 5 ² = 25 y los múltiplos de 7 a partir de 7 ² = 49. Los múltiplos por debajo del cuadrado siempre se han marcado con un factor menor. Al hacer clic en la imagen se accede a File:Sieve of Eratosthenes animation.gif, que también lo explica. PrimeHunter ( discusión ) 18:46 18 sep 2017 (UTC) [ responder ]

Probablemente quisiste decir "Los múltiplos por debajo del cuadrado ya han sido marcados con un factor menor". Solo lo señalo para beneficio de los futuros lectores. WillNess ( discusión ) 17:51 29 abr 2018 (UTC) [ responder ]

Añadir o eliminar enlace a la teoría del tamiz

Hace un par de días realicé una edición sencilla para eliminar un enlace del título, lo que generalmente se considera de mala educación. Para mantener toda la información intacta, agregué el enlace al final de la oración en lugar de dentro del título.

David Eppstein, autor de este cambio, afirmó que "la teoría de la criba es mucho más avanzada y no es necesaria para explicar esta criba". Por lo tanto, aparentemente cree que no deberíamos incluir este enlace en este artículo. Sin embargo, el autor de este cambio volvió a agregar un enlace a ese artículo.

Siguiendo el ejemplo de David, eliminé el enlace y solucioné ambos problemas a la vez. Luego, WillNess lo modificó y dijo "deshacer según los motivos de la reversión anterior", con lo que hizo exactamente lo contrario de lo que esa reversión pretendía hacer.

En cualquier caso, como parece que la gente quiere editar la guerra por esto, @David Eppstein : ¿debería haber un enlace a la teoría del tamiz en este artículo o no? Maury Markowitz ( discusión ) 11:47 19 mar 2019 (UTC) [ responder ]

Hola, lo siento, debería haber prestado más atención, pensé que habías vuelto a tu versión anterior. Resulta que simplemente eliminaste el enlace del lead. Creo que probablemente debería estar ahí, todavía, ya que le da al lector más para explorar. Si alguna política nos impide esto, es una lástima. Pero la redacción en tu primera edición era demasiado pesada para el lead. WillNess ( discusión ) 12:12 19 mar 2019 (UTC) [ responder ]

Si no es apropiado para el título, y no lo es, elimínelo. En cualquier caso, incluir un enlace fuera del título es de mala educación. Maury Markowitz ( discusión ) 14:10 19 mar 2019 (UTC) [ responder ]

Creo que la teoría del tamiz solo debería mencionarse en el encabezamiento si esa mención sirve para resumir alguna parte sustancial del cuerpo, según MOS:INTRO . Simplemente incluirla en el encabezamiento sin tener nada sobre la teoría del tamiz en el cuerpo del artículo no sirve para ningún propósito explicativo y sirve para hacer que el encabezamiento sea más WP:TECHNICAL cuando deberíamos esforzarnos por hacerlo menos. Definitivamente no debería estar vinculada cuando usamos por primera vez en negrita la frase "tamiz de Eratóstenes" (como la dejó Maury) ya que eso viola MOS:BOLDAVOID , y creo que incluirla en otra parte del encabezamiento podría ser incómodo. Y el intento anterior de Maury de incluirla, agregando "usar una aplicación de la teoría del tamiz " al final de una de las oraciones, no solo hace que la oración sea más larga y más difícil de entender, sino que crea la falsa impresión de que la teoría del tamiz vino primero y este tamiz en particular fue una de sus aplicaciones. De hecho, este tamiz se conocía mucho antes, y la teoría del tamiz recibió su nombre en honor a él. - David Eppstein ( discusión ) 16:04, 19 de marzo de 2019 (UTC) [ respuesta ]

Mis dos centavos: la versión original (que fue modificada por Maury Markowitz) era terrible (por las razones articuladas por varias personas arriba) y quitar el enlace fue bueno. La versión actual parece estar bien; y ¿quizás todos en esta discusión estén contentos con ella? Si alguien quiere hacerlo, me parece que el lugar correcto para agregar un enlace a "teoría del tamiz" sería en el último párrafo del titular, que actualmente dice

Uno de los muchos tamices de números primos , es una de las formas más eficientes de encontrar todos los primos más pequeños. Puede usarse para encontrar primos en progresiones aritméticas .

(citas omitidas). Por ejemplo, aquí se muestra una forma posible de hacerlo:

Es una de las diversas cribas de números primos y una de las formas más eficientes de encontrar todos los primos más pequeños. Puede utilizarse para encontrar primos en progresiones aritméticas . El estudio de las generalizaciones de la criba de Eratóstenes se denomina teoría de cribas .

Pero también sería un miembro perfecto de una sección "Ver también". -- JBL ( discusión ) 16:17 19 mar 2019 (UTC) [ responder ]

No estoy seguro de que generalizaciones del tamiz de Eratóstenes sea una expresión correcta (la palabra generalizaciones suena un poco fuera de lugar en este contexto), pero una oración en ese sentido me parece una buena idea. XOR'easter ( discusión ) 16:36 19 mar 2019 (UTC) [ responder ]

Estoy de acuerdo con David en que el enlace a la teoría del tamiz está mal ubicado en la primera oración. También estoy de acuerdo en que el enlace a la teoría del tamiz debe aparecer al final de la introducción. Debe estar allí para dar contexto, pero también porque el artículo presenta algunas variantes que son tamices pero no exactamente el de Erastótenes. Por lo tanto, sugiero reemplazar el último párrafo de la introducción por

La criba de Eratóstenes es la más antigua y sencilla de una familia de algoritmos que funcionan de forma similar y por ello se denominan cribas . Algunas, las cribas de números primos , se utilizan para el cálculo rápido de números primos pequeños. Otras cribas se utilizan para generar otros subconjuntos de los números naturales y para estimar el número de sus elementos hasta un límite determinado.

Por cierto, la capitalización de "Sieve" después del artículo me parece extraña. En mi opinión, o se debería eliminar el artículo o "sieve" debería dejarse sin mayúsculas. Esta es una pregunta para hablantes nativos de inglés. D.Lazard ( discusión ) 17:34 19 mar 2019 (UTC) [ responder ]

Prefiero que el hilo actual siga intacto y que el enlace se añada a la sección Ver también. Mantenga el hilo simple para facilitar la accesibilidad general. Si es necesario, se pueden añadir detalles técnicos en alguna parte del cuerpo. WillNess ( discusión ) 08:07 20 mar 2019 (UTC) [ responder ]

Por otra parte, la última frase del prólogo parece demasiado corta, así que tal vez sea mejor ampliarla.

Uno de los muchos tamices de números primos, es una de las formas más eficientes de encontrar todos los primos más pequeños. Puede usarse para encontrar primos en progresiones aritméticas. (Aquí está la adición:) El estudio de técnicas generales en teoría de números similares al tamiz se conoce como teoría de tamices .

Algo así. WillNess ( discusión ) 08:19 20 mar 2019 (UTC) [ responder ]

Corrección en tamiz segmentado

Hola,

En la sección de tamiz segmentado se dice que el tamaño del segmento delta debe elegirse menor o igual a sqrt(n). El problema es que entonces el tamiz no encuentra factores primos entre delta y sqrt(n) en segmentos posteriores. ¿No debería ser mayor que sqrt(n)? — Comentario anterior sin firmar agregado por Ovinus Real ( discusión • contribs ) 06:29, 13 de julio de 2020 (UTC) [ responder ]

Si todos los primos cuyos múltiplos deben considerarse pertenecen al primer segmento. De lo contrario, los primos de otros segmentos deben incluirse en "hallados hasta ahora". He editado el artículo para aclarar esto. D.Lazard ( discusión ) 10:02 13 jul 2020 (UTC) [ responder ]

\Delta \geq {\sqrt {n}},

Las tablas de Análisis computacional y Complejidad algorítmica no tienen sentido

No está claro qué intentan mostrar las tablas en Análisis computacional y complejidad algorítmica. "A continuación se muestra una tabla que muestra el número de operaciones realmente medido para una implementación práctica de la criba de Eratóstenes en comparación con el número de operaciones predichas a partir de la expresión anterior", por lo que ni siquiera muestra la implementación. ¿Cómo se utiliza exactamente la factorización de ruedas para optimizar la criba? --Abstractsail (discusión) 07:08, 3 de septiembre de 2020 (UTC) [ responder ]

Denominación del tamiz lineal como "tamiz de Euler"

He revisado la referencia proporcionada http://research.cs.wisc.edu/techreports/1990/TR909.pdf y no veo ninguna mención de Euler. De todos modos, está claro que Euler utilizó las técnicas para pruebas y no como un algoritmo informático para generar números primos en tiempo lineal (no creo que la complejidad temporal haya sido nunca su preocupación en una prueba matemática). Así que no sé de dónde viene realmente el nombre. Wqwt ( discusión ) 20:27 29 oct 2021 (UTC) [ responder ]

Esto solía llamarse algo así como "la versión de tamiz en la prueba de Euler de la función zeta", y luego un editor simplemente lo acortó. Hubo mucha discusión sobre esta versión en Haskell-cafe alrededor de 2010, donde se usó ese nombre corto explícitamente, si es que eso cuenta para algo. (Disculpas por los errores tipográficos, si los hay) -- WillNess ( discusión )

(y la fecha es: ) WillNess ( discusión ) 15:14 28 may 2022 (UTC) [ responder ]

Resulta que no recordaba nada de esto, lo siento. Se presentó como tal de inmediato. Aquí está la primera versión del artículo donde apareció esa sección: https://en.m.wikipedia.org/w/index.php?title=Tamiz_de_Eratóstenes&oldid=282870717 -- WillNess ( discusión ) 15:25 28 may 2022 (UTC) [ responder ]

Optimización faltante en animación y pseudocódigo

Tanto la animación como el pseudocódigo mencionan que incluyen optimización (empezando por los cuadrados primos). El argumento es que todos los números menores que el cuadrado primo ya han sido marcados. Luego va y marca prime^2, prime^2 + prime, prime^2 + 2 * prime, ... pero la mitad de esos números son pares. Por lo tanto, otra optimización común es marcar solo prime^2, prime^2 + 2 * prime, prime^2 + 4 * prime, ... para cualquier primo > 2. Llevando esto un paso más allá, se excluyen todos los números pares de la matriz de booleanos en primer lugar:

El algoritmo Criba de Eratóstenes tiene  como entrada : un entero n > 1. Salida : todos los números primos del 2 al n . Sea  A una matriz de valores booleanos , indexada por el entero s 1 a n /2, Inicialmente todo configurado como verdadero .  para  i = 3, 5, 7, 9, ..., sin exceder  $\sqrt n$   hacer  si  A [ i / 2] es  verdadero  para  j = i ² , i ² +2 i , i ² +4 i , i ² +6 i , ..., sin exceder n  hacer  A [ j / 2 ] := falso devuelve todos los i <= n tales que i == 2 o i  es  impar y A [ i / 2] es  verdadero .

Además de ahorrar tiempo al marcar todos los números pares, también ahorra la mitad de la memoria y, por lo tanto, también es una optimización común.

Sí, esto se menciona en el artículo, pero también debemos simplificarlo. Es un acto de equilibrio. -- WillNess ( discusión )

(aquí está la firma con la fecha, si no recuerdo mal cómo hacerlo) WillNess ( discusión ) 15:13 28 may 2022 (UTC) [ responder ]

Esa es una buena optimización. Puedes simplemente mencionar el tamizado omitiendo los números pares. Se mencionan optimizaciones más simples en https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#sieving-by-the-odd-numbers-only Wqwt ( discusión ) 05:10, 25 de agosto de 2022 (UTC) [ responder ]

Se menciona en la descripción general. WillNess ( discusión ) 14:52 3 oct 2022 (UTC) [ responder ]

¿Tamiz de Sorenson?

¿Estamos casados con la mención del trabajo de Sorenson? Tal vez deberíamos decir algo más, como "... el tamiz ahorrador de espacio atribuido a Dunten, Jones y Sorenson...". La cita también está rota, pero esta no: https://doi.org/10.1016/0020-0190(96)00099-3.

Ni siquiera estoy seguro de que ese sea el autor o artículo correcto al que se refería el colaborador, pero parece que no hay nada a lo que comúnmente se haga referencia como el Tamiz de Sorensen. 69.162.230.42 (discusión) 00:34 15 ago 2024 (UTC) [ responder ]

Encontré un enlace que no estaba tan roto al mismo artículo. Actualicé el texto para hacer referencia al nombre real del Tamiz del artículo, pero también dejé una atribución a J. Sorenson, esto mantiene una atribución con un nombre más correcto. También actualicé la cita a un enlace vivo. Creo que hasta que el Tamiz Primario de Pseudocuadrados sea comúnmente denominado Tamiz Sorenson, deberíamos abstenernos de forzar un nombre.

Me pregunto si algún estudiante suyo agregó esto mientras revisaba el material. 69.162.230.42 (discusión) 00:52 15 ago 2024 (UTC) [ responder ]