Last active
October 12, 2016 17:52
-
-
Save rodrigoSaladoAnaya/518d706d1f45ee63b0d49529a6ccd165 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
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
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
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
¿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