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

# 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/>.

$_=7;
# don't need primes 2 3 5 7 because those are the factors of the modulus 210
for$l('a'..'z','A'..'Z'){
    $_=&nextprime($_);
    $l{$_}=$l;
    print"$l $_\n";
}

print"\n";

#numbers X such that gcd(210,X)==1
@gcdlist=qw(1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
89 97 101 103 107 109 113 121 127 131 137 139 143 149 151 157 163 167
169 173 179 181 187 191 193 197 199 209 );

# global variables
$modulus=2*3*5*7;
$chunksize=4;
$readstdin=1 if defined($ARGV[0]);

&header;
$spacer=0;
# a complicated control structure: read a line from STDIN only if gcd(210, $x)==1
MAIN: for($x=1;;++$x){
    $good=1;
    for$p(qw/2 3 5 7/){
        $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 $modulus\n";
    for(my$place=100;$place>=1;$place/=10){
        my$t;
        if(100==$place){
            $t='';
        }elsif(10==$place){
            $t='div';
        }elsif(1==$place){
            $t=$modulus;
        }else{
            die;
        }
        printf "%-5s",$t;
        my$spacer=0;
        for(@gcdlist){
            if(0==$spacer){
                print " ";
            }
            my$r=$_%$place;
            my$x=($_-$r)/$place;
            if($x){
                print "",$x%10;
            }else{
                print" ";
            }
            ++$spacer;
            $spacer%=$chunksize;
        }
        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
        }}}