#!/usr/bin/perl # # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program. If not, see . # # Copyright (C) 2008 Vino Fernando Crescini # Google Treasure Hunt 2008 Puzzle 4 use strict; use bigint; # we assume that the file contains a list of prime numbers, one prime per # line, and that they're sorted in ascending order sub get_primes { my (\$lparray, \$fname) = @_; if (!open(FH, "<", \$fname)) { return 0; } # instead of just loading the primes, we load the partial sums while(my \$line = ) { if (!(scalar @\$lparray)) { push(@\$lparray, \$line); } else { push(@\$lparray, \$line + \$lparray->[\$#{\$lparray}]); } } close(FH); return 1; } # naive, obviously sub is_prime { my \$num = \$_; my \$sqrt = int sqrt(\$num); if (\$num <= 1) { return 0; } if (\$num <= 3) { return 1; } if ((\$num % 2) == 0 || (\$num % 3) == 0) { return 0; } for (my \$i = 1; 1; \$i++) { my \$t1 = (6 * \$i) + 1; my \$t2 = (6 * \$i) - 1; if ((\$t1 <= \$sqrt && (\$num % \$t1) == 0) || (\$t2 <= \$sqrt && (\$num % \$t2) == 0)) { return 0; } if (\$t1 > \$sqrt && \$t2 > \$sqrt) { return 1; } } } # return the sum of the first n prime numbers starting from offset sub sum_primes { my (\$lparray, \$offset, \$n) = @_; return \$lparray->[\$n + \$offset - 1] - (\$offset ? \$lparray->[\$offset - 1] : 0); } # find the smallest prime number that can be expressed as the sum of # A0, A1, A2, ..., An consecutive prime numbers sub solve { my (\$lparray, \$lnarray, \$sum, \$verbose) = @_; my \$isum = 0; my \$n; if (!scalar(@{\$lnarray})) { return \$sum; } \$n = pop(@\$lnarray); for(my \$i = 0, my \$stop = 0; \$i < (\$#{\$lparray} - \$n) && !\$stop; \$i++) { \$isum = sum_primes(\$lparray, \$i, \$n); if (!\$sum) { # first time if (is_prime(\$isum)) { \$verbose && printf(" found prime %s at %s\n", \$isum, \$n); if (solve(\$lparray, \$lnarray, \$isum, \$verbose)) { # finally! return \$isum; } } } else { # not the first call so we need not check for primality if (\$isum == \$sum) { \$verbose && printf(" matched %s at %s\n", \$isum, \$n); if (solve(\$lparray, \$lnarray, \$isum, \$verbose)) { return \$isum; } } # there is really no point to go on if we exceed the number if (\$isum > \$sum) { \$verbose && printf(" exceeded %s at %s\n", \$isum, \$n); \$stop = 1; } } } # if we got here, we've exhausted all the primes # so put it back \$verbose && printf(" no match for %s at %s\n", \$isum, \$n); push(@\$lnarray, \$n); return 0; } my @parray; my @narray; if (@ARGV < 2) { printf(STDERR "usage: \$0 [ [...]]\n"); exit 1; } for (my \$i = 0; \$i < @ARGV - 1; \$i++) { if (\$ARGV[\$i + 1] !~ m/^[1-9][0-9]*\$/) { printf(STDERR "\"%s\" is not a positive integer\n", \$ARGV[\$i + 1]); exit 2; } push(@narray, int \$ARGV[\$i + 1]); } if (!get_primes(\@parray, \$ARGV)) { printf(STDERR "can't open \"%s\" for reading\n", \$ARGV); exit 3; } @narray = sort { \$a <=> \$b } @narray; printf("%s\n", solve(\@parray, \@narray, 0, (\$ENV{'DEBUG'} != 0))); exit 0;