Created
March 13, 2013 12:02
-
-
Save stepantubanov/5151461 to your computer and use it in GitHub Desktop.
Problem 47.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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