How to resolve the algorithm AKS test for primes step by step in the Factor programming language

Published on 12 May 2024 09:40 PM
#Factor

How to resolve the algorithm AKS test for primes step by step in the Factor programming language

Table of Contents

Problem Statement

The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles. The theorem on which the test is based can be stated as follows: are divisible by

p

{\displaystyle p}

.

Using

p

3

{\displaystyle p=3}

:

And all the coefficients are divisible by 3,   so 3 is prime.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm AKS test for primes step by step in the Factor programming language

Source code in the factor programming language

USING: combinators formatting io kernel make math math.parser
math.polynomials prettyprint sequences ;
IN: rosetta-code.aks-test

! Polynomials are represented by the math.polynomials vocabulary
! as sequences with the highest exponent on the right. Hence
! { -1 1 } represents x - 1.
: (x-1)^ ( n -- seq ) { -1 1 } swap p^ ;

: choose-exp ( n -- str )
    { { 0 [ "" ] } { 1 [ "x" ] } [ "x^%d" sprintf ] } case ;

: choose-coeff ( n -- str )
    [ dup neg? [ neg "- " ] [ "+ " ] if % # ] "" make ;

: terms ( coeffs-seq -- terms-seq )
    [ [ choose-coeff ] [ choose-exp append ] bi* ] map-index ;

: (.p) ( n -- str ) (x-1)^ terms <reversed> " " join 3 tail ;

: .p ( n -- ) dup zero? [ drop "1" ] [ (.p) ] if print ;

: show-poly ( n -- ) [ "(x-1)^%d = " printf ] [ .p ] bi ;

: part1 ( -- ) 8 <iota> [ show-poly ] each ;

: (prime?) ( n -- ? )
    (x-1)^ rest but-last dup first [ mod 0 = not ] curry find
    nip not ;

: prime? ( n -- ? ) dup 2 < [ drop f ] [ (prime?) ] if ;

: part2 ( -- )
    "Primes up to 50 via AKS:" print
    50 <iota> [ prime? ] filter . ;

: aks-test ( -- ) part1 nl part2 ;

MAIN: aks-test

You may also check:How to resolve the algorithm Loops/With multiple ranges step by step in the Raku programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Mercury programming language
You may also check:How to resolve the algorithm Short-circuit evaluation step by step in the Oz programming language
You may also check:How to resolve the algorithm Babbage problem step by step in the Component Pascal programming language
You may also check:How to resolve the algorithm Loops/Break step by step in the MUMPS programming language