Project Euler - Problem 37

問題

• 原文

  Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

• 日本語訳

  右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

解答

考え方はProblem 35と同じで、切り詰めていくと途中で合成数になることが分かっている数を最初に除外しています。 0、4、6、8のいずれかの数字を含む場合は明らかに途中で偶数になりますが、2と5は少し特別で、数の一番上の桁にのみ現れた場合は除外できません。何故なら：

1. 左から切り詰めたときは最初に取り除かれるので関係がない。
2. 右から切り詰めていって最後の1桁になったとき、2と5は素数である。

からです。具体的には23と53がこのケースに該当するので、間違って除外すると処理が終わりません。

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/say state/;
use List::Util qw/sum/;
use List::MoreUtils qw/all none/;

sub is_prime($) {
  state %memos;
  my $n = shift;
  return 0 if $n < 2;
  return 1 if $n == 2;
  return 1 if $n == 3;
  return $memos{$n} if exists $memos{$n};
  $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n;
}

sub is_truncatable_prime($) {
  my $n = shift;
  return 0 if length $n == 1;
  return 0 if $n =~ /[0468]/;
  return 0 if $n =~ /.[25]/;
  return 0 unless is_prime $n;
  all {
    is_prime substr($n, $_) and is_prime substr($n, 0, -$_)
  } 1 .. length($n) - 1;
}

my @truncatables;
for (my $i = 11; @truncatables != 11; $i += 2) {
  push @truncatables, $i if is_truncatable_prime $i;
}
say sum @truncatables;