1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다.
2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?
1~9까지 합이 45이고, 1~8까지 합이 36이다. 이들의 합은 모두 3의 배수이고, 각 자릿수의 합이 3의 배수이면, 3의 배수이므로 9자리 팬디지털과 8자리 팬디지털은 3의 배수가 된다.
따라서 7자리 팬디지털 까지만 체크하면 된다.
중복없이 팬디지털을 생성하기 위해 Math::Permute::Array 모듈을 사용했다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Permute::Array; use Math::Prime::Util ':all'; my $r = 0; for (1..7) { my @a = (1..$_); my $p = new Math::Permute::Array(@a); for my $i (0..$p->cardinal()-1) { my $s = join("", @{$p->permutation($i)}); $r = $s if ($r < $s and is_prime($s)); } } say $r; |