I was watching this today… Learn Ruby Programming – Day 17 – Find Prime Numbers

well almost half way through before I decided to run it myself

note: it’s not an exact copy but the core is the same

def find_prime(x,y) prime = [] while (x <= y) prime_flag = true i = 2 while (i <= x/2) if x%i == 0 prime_flag = false break end i +=1 end if prime_flag prime << x end x+=1 end prime end

and someone suggested to use #find

def prime_between(x,y) prime = [] while x <= y result = (2..x).find{|i| x%i == 0} prime << x if result == x x +=1 end prime end

Yep #prime_between is definitely much neater than #find_prime, but how about the time?

t = Time.now 10.times{find_prime(7,100)} puts "#find_prime: #{Time.now - t}" t = Time.now 10.times{prime_between(7,100)} puts "#prime_between: #{Time.now - t}" #and in case you wanna see benchmark require "benchmark" time = Benchmark.measure do find_prime(7,100) end puts time time1 = Benchmark.measure do prime_between(7,100) end puts time1

————- result

time 1: 0.000462

time 2: 0.001452

——————-

0.000000 0.000000 0.000000 ( 0.000052)

0.000000 0.000000 0.000000 ( 0.000167)

So even though #prime_between is neater, it’s slower… noted that #find_prime goes up to x/2

#... while (i <= x/2)

whereas #prime_between goes up to x

#... result = (2..x).find{|i| x%i == 0}

so in worst case scenario, #prime_between is obviously going to run longer…

so I updated #prime_between

def prime_between(x,y) prime = [] while x <= y result = (2..x/2).find{|i| x%i == 0} prime << x if result.nil? x +=1 end prime end

updated benchmark:

#find_prime: 0.000463

#prime_between: 0.001015

——————-

0.000000 0.000000 0.000000 ( 0.000052)

0.000000 0.000000 0.000000 ( 0.000127)

Hmmm… yep a little faster than the previous #prime_between but still slower than #find_prime.

Anyway, here’s another one inspired by Sieve of Eratosthenes

def sieve_prime(x,y) prime = (x..y).to_a while (x<=y) (2..Math.sqrt(x)).each do |i| if x%i == 0 prime -= [x] break end end x +=1 end prime end