Skip to content

Instantly share code, notes, and snippets.

@stepantubanov
Created March 13, 2013 12:02
Show Gist options
  • Save stepantubanov/5151461 to your computer and use it in GitHub Desktop.
Save stepantubanov/5151461 to your computer and use it in GitHub Desktop.
Problem 47.
require 'rspec/autorun'
def prime_numbers_generator
current = 2
loop do
possible_divisors = 2.upto(current / 2)
unless possible_divisors.find { |divisor| current % divisor == 0 }
yield current
end
current += 1
end
end
class EnumeratorCache
def initialize(enumerator)
@enumerator = enumerator
@cached = []
end
def enumerate
@cached.each do |cached|
yield cached
end
loop do
current = @enumerator.next
@cached << current
yield current
end
end
def enumerator
to_enum(:enumerate)
end
end
def prime_numbers
@cache ||= EnumeratorCache.new(to_enum(:prime_numbers_generator))
@cache.enumerator
end
describe EnumeratorCache do
let(:enumerator) { stub }
subject { EnumeratorCache.new(enumerator) }
let(:cached) { subject.enumerator }
let(:value) { stub }
before do
enumerator.stub(:next).and_return(value)
end
it 'acts like underlying enumerator' do
enumerator.should_receive(:next).once
cached.next.should == value
end
it 'uses saved values on second run' do
enumerator.should_receive(:next).once
subject.enumerator.next.should == value
subject.enumerator.next.should == value
end
end
describe 'prime_numbers' do
it 'enumerates prime numbers' do
prime_numbers.next.should == 2
end
it 'computes only what is needed' do
prime_numbers.first(4).should == [2, 3, 5, 7]
end
end
# Find the first four consequtive integers to have four distinct prime factors.
require 'rspec/autorun'
require_relative 'prime_numbers'
def prime_factors(number)
factor = prime_numbers.find do |prime_number|
number % prime_number == 0
end
factors = []
begin
number /= factor
factors << factor
end while number % factor == 0
if number > 1
factors.concat prime_factors(number)
end
factors
end
describe 'prime_factors' do
it 'returns prime number itself' do
prime_factors(3).should == [3]
end
it 'produces multiple prime factors' do
prime_factors(6).should == [2, 3]
end
it 'properly handles repeat numbers' do
prime_factors(12).should == [2, 2, 3]
end
end
def find_four_integers
current = 2
distinct_factors = []
loop do
distinct_factors << prime_factors(current).uniq
distinct_factors.shift if distinct_factors.size > 4
if distinct_factors.all? { |f| f.size == 4 }
four_integers = ((current - 3)..current).to_a
puts "Solution: #{four_integers.join(', ')}"
break
end
current += 1
puts(current) if current % 1000 == 0
end
end
find_four_integers
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment