use strict;
use Term::ANSIColor;
use Math::Prime::Util;

my $a;
my $n = $ARGV[0];
my $p;
foreach (@{ Math::Prime::Util::primes(0,30_000_000) }) { $p->{$_} = 1; }

my $row_items = 1;
my $i = 1;
foreach my $row (1..$n) {
    #printf q[ ] x ($n - $row);
    foreach my $row_item (1..$row_items) {
        my $found_primes = 0;
        foreach my $num (1..$n) {
            my $i_this = $i + ($row_item - 1) + (($num - 1) * $row_items);
            $found_primes ++ if (exists $p->{$i_this});
        }
        #printf "%s", $found_primes ? colored(['bright_red on_bright_green'], " ") : colored(['black on_bright_red'], " ");
        $a->[$row_item][$row] = $found_primes ? 'G' : 'R';
    }
    $i += $row_items * $n;
    $row_items += 1;
    #printf "\n";
}
#exit;
my $painted;
do {
    $painted = 0;
    foreach my $row (1..$n) {
        foreach my $row_item (1..$row) {
            if (($a->[$row_item+0][$row+0] =~ m~[Rr]~) && ($a->[$row_item+0][$row+1] =~ m~[Rr]~) && ($a->[$row_item+1][$row+1]) eq 'G') {
                $painted ++;
                $a->[$row_item+1][$row+1] = 'r'; # bottom right
            }
            if (($a->[$row_item+0][$row+0] =~ m~[Rr]~) && ($a->[$row_item+0][$row+1] =~ m~[Rr]~) && ($a->[$row_item-1][$row+0]) eq 'G') {
                $painted ++;
                $a->[$row_item-1][$row+0] = 'r'; # top left
            }
            if (($a->[$row_item+0][$row+0] eq 'G') && ($a->[$row_item-1][$row+0] =~ m~[Rr]~) && ($a->[$row_item+1][$row+1]) =~ m~[Rr]~) {
                $painted ++;
                $a->[$row_item+0][$row+0] = 'r';
            }
            if (($a->[$row_item+0][$row+0] =~ m~[Rr]~) && ($a->[$row_item+1][$row+1] eq 'G') && ($a->[$row_item+2][$row+1]) =~ m~[Rr]~) {
                $painted ++;
                $a->[$row_item+1][$row+1] = 'r';
            }
        }
    }
    #printf qq[loop\n];
} while ($painted > 0);
foreach my $row (1..$n) {
    printf q[ ] x ($n - $row);
    foreach my $row_item (1..$row) {
        printf "%s", colored(['bright_red on_bright_green'], " ") if ('G' eq $a->[$row_item][$row]);
        printf "%s", colored(['black on_bright_red'], " ") if ('R' eq $a->[$row_item][$row]);
        printf "%s", colored(['black on_red'], " ") if ('r' eq $a->[$row_item][$row]);
    }
    printf qq[\n];
}