AKS Prime Test as described at http://primes.utm.edu/prove/prove4_3.html Input: Integer n > 1 if (n is has the form ab with b > 1) then output COMPOSITE r := 2 while (r < n) { if (gcd(n,r) is not 1) then output COMPOSITE if (r is prime greater than 2) then { let q be the largest factor of r-1 if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break } r := r+1 } for a = 1 to 2sqrt(r)log n { if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE } output PRIME; aksprime:=proc(n::integer>1) r:=2 while r<n do if igcd(n,r) <> 1 then msg:="Composite";