Autor Tema: Agloritmo Para hallar números primos

0 Usuarios y 1 Visitante están viendo este tema.

16 Noviembre, 2010, 09:59 pm
Leído 1536 veces

gmares

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 225
  • Karma: +0/-0
  • Sexo: Masculino
Saludos!
En realidad quisiera saber como se puede demostrar que para hallar los numeros primos menores a una cota \( k \) usando el método de la Criba de Eratóstenes, solo se deben eliminar del conjunto de los naturales entre el 1 y la cota \( k \), a los multiplos de los números naturales desde el 2 hasta \( [\sqrt[ ]{k}] \). Cuál sería la demostración de este hecho particular?
Desde ya gracias!

16 Noviembre, 2010, 10:49 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Simplemente ten en cuenta que si un número \( n \) no es primo entonces puedes escribirse como producto de dos divisores no triviales \( n=ab \); alguno de ellos ha de ser menor o igual que \( \sqrt{n} \) ya que en otro caso llegaríamos a que:

 \( n=ab>\sqrt{n}\sqrt{n}=n \) IMPOSIBLE

Saludos.

17 Noviembre, 2010, 04:58 am
Respuesta #2

gmares

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 225
  • Karma: +0/-0
  • Sexo: Masculino
Entiendo lo que dices, si \( n \) no es primo entonces puede ser expresado como el producto de dos factores \( a \) y \( b \) y que por ser diferentes uno será forzosamente \( a<\sqrt[ ]{n} \), ya que de ser ambos mayores a \( \sqrt[ ]{n} \) el producto será \( a*b>n \).
Entonces, habiendo extraído los múltiplos de \( a<\sqrt[ ]{n} \), no es necesario extraer los de \( b \) pues este de ser mayor a \( \sqrt[ ]{n} \) entonces no puede estar multiplicado por ningún \( a<\sqrt[ ]{n} \) ya que dicho producto de ser menor o igul a \( n \) ya fué eliminado como múltiplo de \( a \), es decir el producto entre ambos ya fué eliminado de la lista. Luego si buscamos un múltiplo de \( b \) que no haya sido eliminado de la lista, este debe ser forzosamente resultado de un \( a*b \) con \( a>\sqrt[ ]{n} \) pero como se dijo antes, siendo también \( b>\sqrt[ ]{n} \) su producto será \( a*b>n \) lo que es una contradicción.
No me darías una mano con la formalidad? Me cuesta escribirlo de manera estricta. Saludos!

17 Noviembre, 2010, 08:35 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 1) Supón que tienes identificados todos los primos \( p_1,\ldots,p_m \) comprendidos entre \( 1 \) y \( [\sqrt{k}] \).

 2) Sea \( n \) natural, \( [\sqrt{k}]\leq n\leq k \). Entonces tenemos que probar que:

 \( n \) es primo \( \Leftrightarrow{} \) \( n \) no es divisible por ningún \( p_i \), \( i=1,\ldots,m \)

 "\( \Longrightarrow{} \)" es inmediato de la definición de número primo.

 "\( \Longleftarrow{} \)" usa el argumento que expliqué en mi anterior post (si no fuese primo tendría un divisor menor que \( \sqrt{n}\leq \sqrt{k} \) y por tanto tendría un divisor primo de los \( m \) calculados).

Saludos.