#!/usr/bin/perl

use strict;
use warnings;
use Carp ();
local $SIG{__WARN__} = \&Carp::cluck;

sub estPremier
{
    my ($x, $premiers) = @_;
    
    for (my $i = 0 ; $i < @$premiers && $premiers->[$i]**2 <= $x ; $i++)
    {
	return 0 if $x % $premiers->[$i] == 0;
    }
    return 1;
}

sub trouvePremiers
{
    my ($nb) = @_;
    my @premiers = (2);
    my $i = 3;
    while(@premiers != $nb)
    {
	if (estPremier ($i, \@premiers))
	{
	    $premiers[@premiers] = $i;
	}
	$i++;
    }
    return \@premiers;
}

sub decompose
{
    my ($x, $premiers) = @_;
    my $i = 0;
    my @decomposition = (0);
    while ($x != 1)
    {
	if ($x % $premiers->[$i] == 0)
	{
	    $decomposition[$i]++;
	    $x /= $premiers->[$i];
	}
	else
	{
	    $i++;
	    $decomposition[$i] = 0;
	}
    }
    return \@decomposition;
}

sub recompose
{
    my ($decomposition, $premiers) = @_;
    my $x = 1;
    for(my $i = 0 ; $i < @$decomposition ; $i++)
    {
	for(my $j = 1 ; $j <= $decomposition->[$i]; $j++)
	{
	    $x *= $premiers->[$i];
	}
    }
    return $x;
}

sub min
{
    my ($x, $y) = @_;
    return $x if $x < $y;
    return $y;
}

sub pgcdTab
{
    my ($a, $b) = @_;
    my @gcd = ();
    for (my $i = 0 ; $i < @$a && $i < @$b ; $i++)
    {
	$gcd[$i] = min ($a->[$i], $b->[$i]);
    }
    return \@gcd;
}

sub pgcd
{
    my ($a, $b) = @_;
    my $premiers = trouvePremiers 20;
    my $deca = decompose ($a, $premiers);
    my $decb = decompose ($b, $premiers);
    my $decpgcd = pgcdTab($deca, $decb);
    my $pgcdab = recompose($decpgcd, $premiers);
    return $pgcdab;
}

my $nb = 20;
# test trouvePremiers
my $premiers = trouvePremiers $nb;
print "Les $nb premiers nombres premiers sont :\n";
print "$_\n" foreach (@$premiers);

# test decompose
my $deca = decompose (108108, $premiers); 
print "\n2, 3, 0, 1, 1, 1 = ";
print "$_, " foreach (@$deca);
my $decb = decompose (30, $premiers); 
print "\n1, 1, 1 = ";
print "$_, " foreach (@$decb);

#test recompose
print "\n108108 = ";
print (recompose ($deca, $premiers));
print "\n30 = ".(recompose ($decb, $premiers))."\n";

#test pgcdTab
my $gcdab = pgcdTab ($deca, $decb);
print "1, 1 = ";
print "$_, " foreach (@$gcdab);
print "\n";

#test pgcd
print "pgcd(108108, 30) = ".(pgcd 108, 30)." (=6) \n";