1

Mi problema consiste en hallar el enésimo primo El código que escribí funciona bien con números, Pero con números muy grandes no hace lo debido

i = 1
counter = 0
puts 'Digite n'
n = gets.to_i  
def prime?(number)
  cont = 0
  primes = [2, 3, 5, 7, 11]
  primes.each { |prime| cont += 1 if (number % prime).zero?} unless primes.include?(number)
  cont == 0
end
while counter <= n
  if prime?(i)
    counter += 1
    prime = i
  end
  i += 1
end
puts prime 
3
  • Supongo que esto es un ejercicio de clase o algo así, pero sólo por si te sirve de algo, también puedes usar require 'prime'; Prime.prime?(2)
    – Horacio
    el 8 jun. 2018 a las 3:12
  • Aquí hay una respuesta que tal vez te sirva: stackoverflow.com/questions/3594345/…
    – Horacio
    el 8 jun. 2018 a las 3:14
  • 2
    Usando la clase "prime" se puede resolver muy fácil, pero no es la idea. Quería hacerlo a mi manera, de igual forma gracias, el link que me diste me ha dado varias ideas. el 8 jun. 2018 a las 20:34

1 respuesta 1

0

Los problemas sobre números primos son un clásico de ejercicios de algoritmos, para lo cual existen varias soluciones algunas mas o menos performantes que otras, o mas o menos exactas al momento de calcular un primo, te propongo 3 escenarios frecuentes.

Divisiones sucesivas Una forma fácil pero no performante es la de tomar un numero entero y dividirlo por todos los menores que este numero si ningúno excepto el 1 y el mismo numero tienen resultado exacto es primo.

Criba de eratostenes Es la mas usada, la cual se almacena todos los números posibles en una tabla de la cual se van descartando los números no primos según el algoritmo, este suele ser mas performante hasta que tenemos numeros realmente grandes. https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Ruby

Tests de Primalidad (Miller-Rabin) Para números grandes se entra en el campo de las probabilidades con un margen de error aceptable puedes usar un algoritmo de test de primalidad, (Ej: Miller-Rabin) https://rosettacode.org/wiki/Miller–Rabin_primality_test#Ruby, En mis pruebas pude obtener números primos de 12 dígitos con una restricción especifica en tiempos muy cortos https://gist.github.com/joelibaceta/53c0ad818c090ee64370f5e77d3e72eb

Si te preguntas que algoritmo usa la libreríaprime de Ruby, te dejo la ultima discusión sobre como hacer este algoritmo mas rápido https://github.com/ruby/ruby/pull/1786

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.