#!/usr/bin/perl

print "Enter a number: ";
$p = <STDIN>;
chomp($p);
print "\n";

$x = 1; $e = 0; $a = 2;

$k = $p - 1;

while($k > 0) {
    if($k % 2 != 0) {
        $e = 1;
        $x = ($a * $x) % $p;
    }
    else {$e = 0;}
    $a = ($a ** 2) % $p;
    $k = ($k - $e) / 2;
}

if($x == 1) {print "$p is prime\n";}
else {print "$p is not prime\n";}
