1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#!/usr/bin/ruby
@LIMIT = 150_000
@is_prime, @omega = Array.new(@LIMIT, false), Array.new(@LIMIT, 0)
def sieve
  @is_prime[2] = true
  1.step(@LIMIT, 2) { |x| @is_prime[x] = true }
  3.step(Math.sqrt(@LIMIT).to_i, 2) do |i|
    if @is_prime[i]
      (i**2).step(@LIMIT, 2*i) { |x| @is_prime[x] = false }
    end
  end
end

def omega(x)
  return 1 if @is_prime[x]
  current, i, factors = 2, x, []
  until @is_prime[i]
    if @is_prime[current] and i % current == 0 and i != current
      while i % current == 0 and i != current do
        factors << current
        i /= current
      end
    end
    unless @omega[i].zero? # Thus in lookup table.
      @omega[x] = factors.uniq.size + @omega[i]
      return @omega[x]
    end
    break if i == current # Just in case
    i += 1
  end
  factors << x
  @omega[x] = factors.uniq.size;
  return @omega[x]
      
end

def calculate
  sieve
  646.upto(@LIMIT) do |i|
    done = true
    (0..4).each { |j| done = omega(i+j) < 4 ? false : done }
    return i if done
  end
end

start = Time.now
puts "Answer: %d\nThat took %f seconds" % [calculate, Time.now - start]