extract amicable pair - improved version

amicable_pair_improved_versoin.rb

=begin
두 수 220과 284는 약수를 통해 매우 친근한 관계를 맺고 있다.
220의 진약수(자신을 제외한 약수)는 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110인데, 이것들의 합은 284이다.
또 284의 진약수는 1, 2, 4, 71, 142인데, 이것들의 합은 220이다.
서로 다른 친구를 ‘또 다른 나’라고 역설한 피타고라스는 이 두 수에서 우정의 표상을 발견했으며, 이런 수들을 ‘우애수’의 쌍이라고 불렀다.
10000 이하의 숫자들 중에서 우애수 쌍의 목록을 구하라.
=end

# require parallel gem, https://github.com/grosser/parallel, for improve performance
require 'parallel'
require 'benchmark' 

def amicable_pair(number_array)
  amicables = []
  number_array.each do |n|
    next if amicables.include?(n)
    
    amicable_sum = refined_submultiple(n).reduce(0, :+)
    
    next if amicable_sum < n # 1.4 

    if amicable_sum <= number_array[-1] && 
      n == refined_submultiple(amicable_sum).reduce(0, :+) && 
      n != amicable_sum
      amicables.push(*[n, amicable_sum]) 
    end
  end
  amicables
end

def amicable_pair_parellel(max_num)
  result = Parallel.map((1..max_num).each_slice(max_num/5)) do |part|
    amicable_pair(part)
  end

  result.flatten
end

# return 약수
def submultiple(num)
  submul = []
  (1..Math.sqrt(num).ceil).each do |n|
    div_result = num.divmod(n)
    submul.push(*[n, div_result[0]]) if div_result[1] == 0 
  end
  submul
end

# return 진약수
def refined_submultiple(num)
  submultiple(num).tap{|n| n.delete num}
end

puts Benchmark.realtime { puts amicable_pair_parellel(10000).inspect }
# => [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

Improved by reducing range and using parallel process.

Improved by reducing range and using parallel process.

Improved by reducing range and using parallel process.