Optimización de código – Generación de números primos

Estoy tratando de escribir un código para el siguiente problema:

Entrada

La entrada comienza con el número t de casos de prueba en una sola línea (t <= 10). En cada una de las siguientes líneas t hay dos números myn (1 <= m <= n <= 1000000000, nm <= 100000) separados por un espacio.

Salida

Para cada caso de prueba, imprima todos los números primos p de manera que m <= p <= n, un número por línea, los casos de prueba separados por una línea vacía.

Entrada de muestra:

2 1 10 3 5 

Salida de muestra:

 2 3 5 7 3 5 

Mi código:

 def prime?(number) return false if number == 1 (2..number-1).each do |n| return false if number % n == 0 end true end t = gets.strip.to_i for i in 1..t mi, ni = gets.strip.split(' ') mi = mi.to_i ni = ni.to_i i = mi while i <= ni puts i if prime?(i) i += 1 end puts "\n" end 

El código funciona bien, el único problema que tengo es que tarda mucho tiempo cuando se ejecuta en rangos de entrada grandes en comparación con otros lenguajes de progtwigción.

¿Estoy haciendo algo mal aquí? ¿Puede este código optimizarse aún más para un tiempo de ejecución más rápido?

He intentado usar un bucle for, un bucle normal, crear una matriz y luego imprimirla. Alguna sugerencia.

Devuelva verdadero si el número es 2, falso si el número es divisible por 2.

Comience a iterar a 3, en lugar de a 2. Use un paso de dos.

Iterar hasta la raíz cuadrada del número, en lugar del número menos uno.

 def prime?(number) return true if number == 2 return false if number <= 1 or number % 2 == 0 (3..Math.sqrt(number)).step(2) do |n| return false if number % n == 0 end true end 

Esto será mucho más rápido, pero aún no muy rápido, como explica @Technation.

He aquí cómo hacerlo usando el Tamiz de Eratóstenes incorporado en Ruby. Deberá calcular previamente todos los números primos hasta el máximo máximo, que será muy rápido, y luego seleccionar los números primos que se encuentren dentro de cada rango.

 require 'prime' ranges = Array.new(gets.strip.to_i) do min, max = gets.strip.split.map(&:to_i) Range.new(min, max) end primes = Prime.each(ranges.map(&:max).max, Prime::EratosthenesGenerator.new) ranges.each do |range| primes.each do |prime| next if prime < range.min break if prime > range.max puts prime end primes.rewind puts "\n" end 

Así es como funcionan las diferentes soluciones con el rango 50000 200000:

  • ¿Tu primo original? función: 1m49.639s
  • Mi primo modificado? función: 0m0.687s
  • Prime :: EratosthenesGenerator: 0m0.221s

Cuantos más rangos se procesen, más rápido debería ser el método Prime :: EratosthenesGenerator.

Ruby es más lento que otros idiomas, según el idioma con el que lo compares; Ciertamente más lento que C / C ++. Pero su problema no es el lenguaje (aunque influye en el comportamiento del tiempo de ejecución), sino su forma de encontrar números primos. Hay muchos mejores algoritmos para encontrar números primos, como el Tamiz de Eratóstenes o el Tamiz de Atkin . También puede leer la página ” Generando Primes ” en Wikipedia y seguir los enlaces allí.

Por cierto, para el Tamiz de Eratóstenes, incluso hay una pieza de código lista para usar en Stackoverflow . Estoy seguro de que un poco de googlear también se activará para otros algoritmos.

Dado que su problema es encontrar números primos dentro de un cierto rango, este es el código del Tamiz de Eratóstenes encontrado en el enlace anterior modificado para adaptarse a su problema particular:

 def better_sieve_upto(first, last) sieve = [nil, nil] + (2..last).to_a sieve.each do |i| next unless i break if i*i > last (i*i).step(last, i) {|j| sieve[j] = nil } end sieve.reject {|i| !i || i < first} end 

Tenga en cuenta el cambio de "sieve.compact" a un "sieve.reject" más complejo con una condición correspondiente.

    Intereting Posts