prime

Find all prime numbers between x & y

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
Advertisements