Created
November 20, 2012 04:58
-
-
Save humbroll/4116140 to your computer and use it in GitHub Desktop.
extract amicable pair - improved version
This file contains 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
=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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Improved by reducing range and using parallel process.