How to resolve the algorithm AKS test for primes step by step in the uBasic/4tH programming language

Published on 12 May 2024 09:40 PM
#Ubasic/4th

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

Source code in the ubasic/4th programming language

For n = 0 To 9
  Push n : Gosub _coef : Gosub _drop
  Print "(x-1)^";n;" = ";
  Push n : Gosub _show
  Print
Next

Print
Print "primes (never mind the 1):";

For n = 1 To 34
  Push n : Gosub _isprime
  If Pop() Then Print " ";n;
Next

Print
End

                                       ' show polynomial expansions
_show                                  ' ( n --)
  Do
    If @(Tos()) > -1 Then Print "+";
    Print @(Tos());"x^";Tos();
  While (Tos())
    Push Pop() - 1
  Loop

  Gosub _drop
Return

                                       ' test whether number is a prime
_isprime                               ' ( n --)
  Gosub _coef

  i = Tos()
  @(0) = @(0) + 1
  @(i) = @(i) - 1


  Do While (i) * ((@(i) % Tos()) = 0)
    i = i - 1
  Loop

  Gosub _drop
  Push (i = 0)
Return

                                       ' generate coefficients
_coef                                  ' ( n -- n)
  If (Tos() < 0) + (Tos() > 34) Then End
                                       ' gracefully deal with range issue
  i = 0
  @(i) = 1

  Do While i < Tos()
    j = i
    @(j+1) = 1

    Do While j > 0
      @(j) = @(j-1) - @(j)
      j = j - 1
    Loop

    @(0) = -@(0)
    i = i + 1
  Loop
Return

                                       ' drop a value from the stack
_drop                                  ' ( n --)
  If Pop() Endif
Return

You may also check:How to resolve the algorithm Higher-order functions step by step in the SuperCollider programming language
You may also check:How to resolve the algorithm Determine if a string is squeezable step by step in the F# programming language
You may also check:How to resolve the algorithm Special characters step by step in the Haskell programming language
You may also check:How to resolve the algorithm Find the intersection of a line with a plane step by step in the Nim programming language
You may also check:How to resolve the algorithm Priority queue step by step in the Perl programming language