n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.
해쉬를 사용하여 구했다.
어떤 수 n에 대해 키는 n, 해쉬값은 d(n)으로 지정하여 끝까지 구한다.
그 후 ‘키’와 ‘키의 해쉬값을 키로 사용한 해쉬값’이 같은 경우를 찾아 모두 더한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Prime::Util ':all'; my %h; my $r = 0; for (1..10000) { my $t = 0; $t += $_ for (all_factors($_)); $h{$_} = $t + 1; } for (keys %h) { $r += $_ if ($_ != $h{$_} and defined $h{$h{$_}} and $_ == $h{$h{$_}}); } say $r; |