Skip to content

Instantly share code, notes, and snippets.

@gabteles
Created May 10, 2013 02:53
Show Gist options
  • Save gabteles/5552115 to your computer and use it in GitHub Desktop.
Save gabteles/5552115 to your computer and use it in GitHub Desktop.
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.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment