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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm AKS test for primes step by step in the Transd 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 Transd programming language

Source code in the transd programming language

#lang transd

MainModule: {
    poly: (λ n Long()
        (with v Vector([1])
            (for i in Range(n) do
                (append v (/ (* (get v -1) (- (- n i))) (to-Long (+ i 1))))
            )
            (reverse v)
            (ret v)
        )
    ),

    aks_test: (λ n Long() -> Bool()
        (if (< n 2) (ret false))
        (with v (poly n)
            (set-el v 0 (+ (get v 0) 1))
            (ret (not (any Range(in: v 0 -1) (λ (mod @it n)))))
        )
    ),

    _start: (λ (with v Vector()
        (for p in Seq( 12 ) do
            (set v (poly p))
            (textout "(x - 1)^" p " = ")
            (for i in v do (textout :sign i "x^" @idx " "))
            (textout "\n")
        )
        (textout "\nList of primes in 2-62 interval:\n")
        (for p in Seq( 2 62 ) do
            (if (aks_test p) (textout p " "))
        )
    ))
}


  

You may also check:How to resolve the algorithm Stack traces step by step in the Tcl programming language
You may also check:How to resolve the algorithm Bitwise operations step by step in the Z80 Assembly programming language
You may also check:How to resolve the algorithm Zero to the zero power step by step in the Nanoquery programming language
You may also check:How to resolve the algorithm Hailstone sequence step by step in the Mercury programming language
You may also check:How to resolve the algorithm Record sound step by step in the BBC BASIC programming language