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
require 'prime'; Prime.prime?(2)