#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;
use Carp;

=pod

Programming Challenge One: Computing Goldbach numbers.

see: http://en.wikipedia.org/wiki/Goldbach's_conjecture

Program notes:

My solution uses a Sieve of Eratosthenes, using a bit vector.  
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

A few notes: I decided that I wanted my solution to find the 
pair of primes that have the smallest difference.  That wasn't
a requirement of the problem, and in fact not doing so produces 
a solution much more quickly.  

I recalled vaguely that I read an article by Randal Schwartz 
many years ago about computing primes in Perl:

http://www.stonehenge.com/merlyn/UnixReview/col26.html

author: e.maki

=cut

# main loop: read command line args, print goldbach numbers
while ( my $num = shift )
{
    printf "%u = %u + %u\n", $num, goldbach( $num );
}

sub goldbach
{
    my $num = shift;
    croak( "Number must be an even integer larger than 2" )
        unless $num > 2 and not $num % 2;

    # not strictly necessary, but predeclare the full 
    # length of the bit vector, to avoid reallocs
    my $sieve = "\0" x ( 1 + ( $num / 8 ));

    for my $i ( 2 .. $num - 1 )
    {
        # skip anything we marked as a composite number
        next if vec( $sieve, $i, 1 );

        # Punch out the composites of this prime from the sieve.
        # thanks to arguile for reminding me that I only need to 
        # start punching composites starting at the square
        # since I've already covered those smaller with the preceding 
        # primes.  (Also, he noticed a bug in my initial increments)
        my $j = $i ** 2;
        vec( $sieve, $j += $i, 1 ) = 1
            while $j < $num;

        # arguile pointed out, I could make this 
        #   next if $i ** 2 < $num;
        # because I can be confident that all composites are accounted 
        # for up to $I ** 2 (ie. the sieve is fully punched to that point)
        # that yields a faster solution, but mine yields the solution with 
        # the smallest difference, as I'll pick the first solution after
        # the midway point.
        next if $num - $i > $i;

        # solution found if the other half of the pair is also prime
        return ( $i, $num - $i )
            if vec( $sieve, $num - $i, 1 ) == 0;
    }
}