서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.
14 = 2 × 7
15 = 3 × 5서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?
해쉬를 이용하여 좀 더 빠르게 구한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Prime::Util ':all'; my $n = 0; while (++$n) { if (f($n) == 4 and f($n+1) == 4 and f($n+2) == 4 and f($n+3) == 4) { say $n; exit; } } my %h; sub f { my $n = shift; return $h{$n} if defined $h{$n}; my ($i, %s, @r); foreach my $i (factor($n)) { push(@r, $i) unless $s{$i}++; } $h{$n} = $#r+1; return $#r+1; } |