Skip to content

Instantly share code, notes, and snippets.

@rodrigoSaladoAnaya
Last active October 12, 2016 17:52
Show Gist options
  • Save rodrigoSaladoAnaya/518d706d1f45ee63b0d49529a6ccd165 to your computer and use it in GitHub Desktop.
Save rodrigoSaladoAnaya/518d706d1f45ee63b0d49529a6ccd165 to your computer and use it in GitHub Desktop.
def get_atmos_list = { input ->
def time_start = System.currentTimeMillis()
def atoms = [2, 3]
def fill_list = { n ->
def sqrt = Math.sqrt(n) as int
def is_atom = true
for(i = 0; i <= sqrt - 1; i++) {
if(n % atoms[i] == 0) {
is_atom = false
return
}
}
if(is_atom) { atoms << n }
}
def next = 4
while(next < input) {
fill_list(next++)
}
def time_end = System.currentTimeMillis()
def time_diff = (time_end - time_start)
return [
atoms: atoms,
time: time_diff
]
}
//println get_atmos_list(10)
//println get_atmos_list(100)
//println get_atmos_list(1000)
//println get_atmos_list(10000)
println get_atmos_list(1_00_000)
@yngwie74
Copy link

yngwie74 commented Oct 11, 2016

¿Y si en lugar de la comprobación de números pares (next % 2 != 0) y la operación de incremento posterior, usas (next += 2)?
next se inicializa a 5 y si siempre le sumas 2, el módulo resulta redundante.

También, como la iteración siempre la comienzas en 1, el primer "atom" en realidad no es necesario, por lo que si lo eliminas y comienzas tu iteración en 0, el algoritmo sigue funcionando. Lo que es más, con este cambio es posible renombrar la lista de "atoms" a un nombre más significativo como "primes", "prime_factors", "previous_primes", etc.

Algo que noté es que esta versión no regresa en n-ésimo primo, como la que publicaste en http://www.javamexico.org/blogs/rodrigo_salado_anaya/coding_dojo_2, si no que esta regresa una "lista de primos menores que n", ¿correcto?

Saludos

@rodrigoSaladoAnaya
Copy link
Author

Para dejar rastro de la 1ra versión:

def get_atmos_list = { input ->
  def time_start = System.currentTimeMillis()
  def atoms = [1, 2, 3]
  def sq = []
  def fill_list = { n ->
    def sqrt = Math.sqrt(n)
    def is_atom = true
    for(i = 1; i <= sqrt; i++) {
      def cn = atoms[i]
      if(n % cn == 0) {
        is_atom = false
        return
      }
    }
    if(is_atom) { atoms << n }
  }
  def next = 5
  while(next < input) {
    if(next % 2 != 0) { fill_list(next) }
    next++
  }
  def time_end = System.currentTimeMillis()
  def time_diff = (time_end - time_start)
  def f = new File("./${input}_${System.currentTimeMillis()}.txt")
  f.write(atoms.join('\n'))
  println "[${input} -> ${atoms.size()}][${atoms.last()}] (${time_diff})..."
  return atoms
}


get_atmos_list(10_000_000) // OUTPUT: [10000000 -> 664580][9999991] (283173)...
//get_atmos_list(32_416_190_071) // TODO

@rodrigoSaladoAnaya
Copy link
Author

rodrigoSaladoAnaya commented Oct 12, 2016

Estaba jugando mucho con la idea de hacer mi versión de la https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes para entenderla del todo y para entenderlo mejor al final tuve que hacer otra versión pero con JS: https://rodrigosaladoanaya.github.io/criba_eratostenes/index.js

https://github.com/rodrigoSaladoAnaya/criba_eratostenes

@rodrigoSaladoAnaya
Copy link
Author

Incluso en la versión WEB uso lo que comentas de n=+2 :P https://github.com/rodrigoSaladoAnaya/criba_eratostenes/blob/master/index.js#L26

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment