#!perl -w
# print the smallest factor of numbers in a compact table.

# run with no arguments, use built-in (slow) factoring routine.

# run with any argument (value of the argument ignored), read a list
# of smallest factor from stdin, e.g., pipe the output of this pari/gp
# command:

# for(n=2,+oo,print(n," ",factor(n)[1,1]))

# Copyright 2021 Ken Takusagawa

# 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 <http://www.gnu.org/licenses/>.


$_=1;
for$l('a'..'z','A'..'Z'){
    $_=&nextprime($_);
    $l{$_}=$l;
    print"$l $_\n";
}

print"\n";

# global variables
$modulus=100;
$chunksize=4;
$readstdin=1 if defined($ARGV[0]);

&header;
$spacer=0;
# a complicated control structure: read a line from STDIN only if gcd(10, $x)==1
MAIN: for($x=1;;++$x){
    $good=1;
    for$p(qw/2 5/){
        $good=0 unless $x % $p;
    }
    next unless $good;
    $b=$x%$modulus;
    $a=$x-$b;
    die if $a%$modulus;
    $a/=$modulus;

    if(1==$b){
        printf'%5d',$a;
    }
    if(1==$x){
        $f=1;
    }elsif($readstdin){
        for(;;){
            last MAIN unless defined($_=<STDIN>);
            die unless ($y,$f)=/^(\d+) (\d+)$/;
            die if$y>$x;
            if($y==$x){
                last;
            }
        }
    }else{
        $f=&factor($x);
    }
    die if $x % $f;
    unless($spacer){
        print" ";
    }
    ++$spacer;
    $spacer%=$chunksize;

    if($f==$x){
        print".";#prime
    }else{
        $_=$l{$f};
        unless(defined){
            $_="*";
            $e.=sprintf' %02d:%d',$b,$f;
        }
        print;
    }
    if($b+1==$modulus){
        if($e){
            #printf'%4s%s',"",$e;
            print$e;
            undef$e;
        }
        print"\n";
        $spacer=0;
    }
}

sub header {
    print "\\"," "x5,"mod 100\n";
    #printf'%4s',"";
    my$indent= "."x5;
    #print$indent;
    printf'%-5s','div';
    for my$b(0..9){
        print" ";
        for my$j(qw(1 3 7 9)){
            print$b
            }}
    print"\n";
    printf "%-5s",'100';

    for my$b(0..9){
        print" ";
        for my$j(qw(1 3 7 9)){
            print$j
            }
    }
    print"\n";
}

#smallest prime factor
sub factor (){
    my$d=shift;
    if($d<4){
        return$d
    }
    for(my$i=2;;++$i){
        if($d%$i==0){
            return$i
        }
        #optimization
        if($i*$i>$d){
            return$d;#prime
        }
    }
}

#strictly greater than
sub nextprime(){
    my$n=shift;
    ++$n;
    for(;;++$n){
        if(&factor($n)==$n){
            return$n
        }}}