rework challenge-076-01 using goldbach's conjecture

looking through the other solutions i found this reference in @andinus
blog article:

https://stackoverflow.com/questions/35755825/find-minimum-prime-numbers-which-sum-to-a-given-value/35756072#35756072

I reworked my brute force solution to make use of the conjecture
assuming it is true for any N that will ever be feed to this programm.
The conjecture has been shown to hold for any $N < 4x10^18 which should
be sufficiently large.

1 files changed, 33 insertions, 26 deletions

diff --git a/challenge-076/alexander-pankoff/perl/ch-1.pl b/challenge-076/alexander-pankoff/perl/ch-1.pl
index bd340b8e07..f191517b4e 100755
--- a/challenge-076/alexander-pankoff/perl/ch-1.pl
+++ b/challenge-076/alexander-pankoff/perl/ch-1.pl
@@ -1,18 +1,18 @@
 #!/usr/bin/env perl
 use strict;
 use warnings;
-use feature qw(signatures say);
+use feature qw(signatures say state);
 no warnings qw(experimental::signatures);
 
 use Scalar::Util qw(looks_like_number);
 use List::Util qw(any first);
 use Memoize;
 
-memoize( '_minimum_primes' );
+memoize( 'is_prime' );
 
 my ( $N ) = @ARGV;
 
-if ( !looks_like_number( $N ) || $N < 2 ) {
+if ( $N =~ m/\D/ ) {
     usage();
     exit 1;
 }
@@ -22,35 +22,42 @@ my ( $number_of_primes_used, $primes_used ) = minimum_primes( $N );
 say $number_of_primes_used;
 say 'Primes used: ' . join( ', ', @$primes_used ) if $ENV{DEBUG};
 
-sub minimum_primes($N) {
-    my @primes_up_to_n = primes( $N );
-    _minimum_primes( $N, \@primes_up_to_n );
-}
-
-sub _minimum_primes ( $N, $primes ) {
-    return ( 1, [$N] ) if any { $N == $_ } @$primes;
-
-    my $minimum = undef;
-    my $used    = [];
-    for my $i ( grep { $_ <= $N } @$primes ) {
-        my ( $count, $acc ) = _minimum_primes( $N - $i, $primes );
-        next if !$count;
+sub minimum_primes ( $N ) {
+    if ( $N < 2 ) {
+        die "cannot construct numbers smaller than 2 from a sum of primes";
+    }
 
-        if ( !$minimum || $count < $minimum ) {
-            $minimum = $count + 1;
-            $used    = [ @$acc, $i ];
+    if ( is_prime( $N ) ) {
+        return ( 1, [$N] ) if is_prime( $N );
+    }
+    elsif ( $N % 2 == 0 ) {
+        my $prime_gen = new_prime_gen( $N );
+        while ( 1 ) {
+            my $prime = $prime_gen->();
+            if ( is_prime( $N - $prime ) ) {
+                return ( 2, [ $N - $prime, $prime ] );
+            }
         }
     }
-
-    return ( $minimum, $used );
+    elsif ( is_prime( $N - 2 ) ) {
+        return ( 2, [ 2, $N - 2 ] );
+    }
+    else {
+        my $is_even = $N - 3;
+        my ( $count, $primes_used ) = minimum_primes( $is_even );
+        return ( $count + 1, [ 3, @$primes_used ] );
+    }
 }
 
-sub primes($max) {
-    grep { is_prime( $_ ) } 0 .. $max;
+sub new_prime_gen($max) {
+    return sub {
+        state $last = 0;
+        $last = first { is_prime( $_ ) } ( $last + 1 ) .. $max;
+        return $last;
+    }
 }
 
-sub is_prime {
-    my ( $n ) = @_;
+sub is_prime ( $n ) {
 
     return 0 if $n <= 1;
     return 1 if $n <= 3;
@@ -70,6 +77,6 @@ sub usage() {
 $0 <N>
 
   Calculate the minimum number of prime numbers required, whose summation gives N
-  <N> a positive number >= 2
+  <N> a positive integer >= 2
 END
 }