Checa a se um número é primo ou não, a partir da divisão do processamento em Threads do Ruby, fazendo a velocidade aumentar consideravelmente. Os testes ainda não foram concluídos, mas o código já apresenta bons resultados.

primeCheck.rb

class << Math
  # Checa se um número é primo ou não.
	#
	# value          - Valor que deverá ser checado
	# checksByThread - Quantidade de checagens por thread. 
	#                  Ajuda a driblar o processamento com valores menores
	#                  Ajuda a driblar a utilização de recursos com valores maiores
	#
	def isPrime?(value, checksByThread = 10**10)
		# Rotina para checagem de número primos
		#
		# from  - Divisor inicial
		# to    - Divisor final
		# value - Valor que deve ser checado
		#
		# from deve obrigatoriamente ser um número ímpar, para
		# garantir o funcionamento da rotina. A checagem desta
		# obrigatoriedade não foi incluída para garantir maior
		# velocidade.
		#
		# A rotina se baseia apenas no resto da divisão entre
		# o valor e os números ímpares entre from e to.
		def PrimeCheckRoutine(from, to, value)
			(from..to).step(2){|i|
				next if value == i
				return false if value % i == 0
			}
			return true
		end

		# Retorna verdadeiro caso o número seja 2
		return true  if value == 2
		
		# Retorna falso caso o valor seja menor que 3
		# ou seja divisível por dois. Penso que checar
		# o último bit é melhor que recorrer ao método
		# do resto da divisão por dois, levando em conta
		# que números grandes podem aparecer por aqui.
		return false if (value < 3) or (value & 1 == 0)
		
		# Array que armazena os threads de verificação criados
		threads = []
		
		# Valor inicial da checagem
		checkDiv = 3
		
		# Computa a raiz quadrada do valor. Se o número não puder
		# ser dividido por nenhum número até sua raiz quadrada,
		# ele é primo.
		valueSqrt = Math.sqrt(value).floor + 1 # Ou (value ** 0.5).floor + 1 ?
		
		# Até que o valor inicial supere a raiz
		until checkDiv > valueSqrt
			# Calcula o limite superior
			nextCDiv = checkDiv + checksByThread
			nextCDiv = value if value < nextCDiv
			
			# Cria thread, informando limite inferior, superior,
			# valor e apontando a rotina que deverá ser seguida.
			thread = Thread.new(checkDiv, nextCDiv, value, &method(:PrimeCheckRoutine))
			
			# Insere thread criado na array de threads
			threads.push(thread)
			
			# Recalcula limite inferior
			checkDiv = nextCDiv + 1
		end
		
		# Retorna verdadeiro se nenhuma verificação nos threads retornou falso
		return threads.all?
	end
end

# Teste
require 'prime'
Prime.each{|i| 
  p i
  p "OOOOOOPS. Fail at #{i}" unless Math.isPrime?(i) 
}