package prime;
use Carp;
use strict;

sub is_prime2
{
	my $n = shift;
	
	if ($n < 8) {
		if ($n == 2 || $n == 3 || $n == 5 || $n == 7) {
			return 1;
		}
		return 0;
	}
	if  ($n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0 || $n % 7 == 0) {
		return 0;
	}
	for (my $i = 11; $i * $i < $n; ) {
		if ($n % $i == 0) {
			return 0;
		}
		$i += 2;
		if ($n % $i == 0) {
			return 0;
		}
		$i += 4;
	}
	
	return 1;
}

sub is_prime
{
	my $n = shift;
	my $prime = shift;
	
	if ($n < 8) {
		if ($n == 2 || $n == 3 || $n == 5 || $n == 7) {
			return 1;
		}
		return 0;
	}
	if  ($n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0 || $n % 7 == 0) {
		return 0;
	}
	
	if (! $prime) {
		my @p = make_prime_table($n);
		$prime = \@p;
	} else {
		if ($prime->[-1] * $prime->[-1] < $n) {
			croak("sqrt($n) > prime array\n");
		}
	}
	
	for (my $i = 0; $i < @$prime; ++$i) {
		my $p = $prime->[$i];
		if ($p * $p > $n) {
			return 1;
		}
		if ($n % $p == 0) {
			return 0;
		}
	}
	
	return 1;
}

sub make_prime_table
{
	my $max = shift;
	my @t = ();
	my @prime = qw(2 3 5 7);
	
	for (my $i = 2; $i < $max; ++$i) {
		if ($i % 2 == 0 || $i % 3 == 0 || $i % 5 == 0 || $i % 7 == 0) {
			next;
		}
		if (! $t[$i]) {
			push(@prime, $i);
			for (my $j = 1; $j * $i < $max; ++$j) {
				$t[$j * $i] = 1;
			}
		}
	}
	return @prime;
}

sub get_prime_divisor
{
	my $x = shift;
	my $n = $x;
	my $prime = shift;
	my @t = ();
	
	if (! $prime) {
		my @p = make_prime_table($n);
		$prime = \@p;
	}
	my $max = $n;
	foreach my $p (@$prime) {
		if ($max < $p) {
			last;
		}
		my $s = 0;
		while ($n % $p == 0) {
			$s = $p;
			$n /= $p;
		}
		if ($s != 0) {
			push(@t, $s);
		}
		if ($n == 1) {
			last;
		}
	}
	if ($n != 0) {
		push(@t, $n);
	}
	pop(@t);
	return @t;
}

sub divisor_sum
{
	my $x = shift;
	my $n = $x;
	my $prime = shift;
	my @t = ();
	
	if (! $prime) {
		my @p = make_prime_table($n);
		$prime = \@p;
	}
	my $max = $n;
	foreach my $p (@$prime) {
		if ($max < $p) {
			last;
		}
		my $s = 1;
		while ($n % $p == 0) {
			$s *= $p;
			$n /= $p;
		}
		if ($s != 1) {
			push(@t, $s);
		}
		if ($n == 1) {
			last;
		}
	}
	if ($n != 0) {
		push(@t, $n);
	}
	my $s = 1;
	foreach my $p (@t) {
		my $k = 1 + ($p == 1 ? 0:$p);
		for (my $i = 2; $i <= int($p / 2); ++$i) {
			if ($p % $i == 0) {
				$k += $i;
			}
		}
		$s *= $k;
	}
	return $s - $x;
}

1;