123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 20 August 2017
- # https://github.com/trizen
- # https://projecteuler.net/problem=425
- # Runtime: 8 min, 23 sec
- use 5.010;
- use strict;
- use ntheory qw(primes);
- use List::Util qw(shuffle);
- my $limit = 10**7;
- # Array of primes up to limit
- my @primes = @{primes($limit)};
- # Table of primes up to limit
- my %h;
- @h{@primes} = ();
- my %seen;
- my %lens;
- # Group by length
- foreach my $p (@primes) {
- push @{$lens{length($p)}}, $p;
- }
- # Group by difference of one digit
- my %table;
- foreach my $len (sort { $b <=> $a } keys %lens) {
- foreach my $p (@{$lens{$len}}) {
- foreach my $i (0 .. $len - 1) {
- my $t = $p;
- substr($t, $i, 1, 'x');
- push @{$table{$t}}, $p;
- }
- }
- }
- sub is_twos_relative {
- my ($n, $m) = @_;
- # If we reach `n=2`, then `m` is a 2's relative
- return 1 if $n == 2;
- # If `n` was already seen, then `m` is not a 2's relative
- if (exists $seen{$n}) {
- return 0;
- }
- undef $seen{$n}; # mark `n` as seen
- # If removing one digit from the left is still a prime
- if (exists($h{substr($n, 1)})) {
- # Is this prime connected to `m` via 2? Great! We're done!
- if (is_twos_relative(substr($n, 1), $m)) {
- return 1;
- }
- }
- # Create the keys that differ in exactly one digit from n
- my @comb;
- foreach my $i (0 .. length($n) - 1) {
- my $t = $n;
- substr($t, $i, 1, 'x');
- push @comb, $t;
- }
- # For each key, iterate over the corresponding primes
- foreach my $c (shuffle(@comb)) {
- foreach my $p (@{$table{$c}}) {
- # We're not interested in p > m
- if ($p > $m) {
- last;
- }
- # Is `p` connected to `m` via 2? Great! We're done!
- if (is_twos_relative($p, $m)) {
- return 1;
- }
- }
- }
- return 0;
- }
- # Sum the primes which are not 2's relatives.
- my $sum = 0;
- foreach my $p (@primes) {
- if (not is_twos_relative($p, $p)) {
- $sum += $p;
- }
- undef %seen; # reset the `seen` table
- }
- say $sum;
|