How to resolve the algorithm AKS test for primes step by step in the Raku programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm AKS test for primes step by step in the Raku 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 Raku programming language
Source code in the raku programming language
constant expansions = [1], [1,-1], -> @prior { [|@prior,0 Z- 0,|@prior] } ... *;
sub polyprime($p where 2..*) { so expansions[$p].[1 ..^ */2].all %% $p }
# Showing the expansions:
say ' p: (x-1)ᵖ';
say '-----------';
sub super ($n) {
$n.trans: '0123456789'
=> '⁰¹²³⁴⁵⁶⁷⁸⁹';
}
for ^13 -> $d {
say $d.fmt('%2i: '), (
expansions[$d].kv.map: -> $i, $n {
my $p = $d - $i;
[~] gather {
take < + - >[$n < 0] ~ ' ' unless $p == $d;
take $n.abs unless $p == $d > 0;
take 'x' if $p > 0;
take super $p - $i if $p > 1;
}
}
)
}
# And testing the function:
print "\nPrimes up to 100:\n { grep &polyprime, 2..100 }\n";
You may also check:How to resolve the algorithm Primality by trial division step by step in the Action! programming language
You may also check:How to resolve the algorithm Lucas-Lehmer test step by step in the Julia programming language
You may also check:How to resolve the algorithm Miller–Rabin primality test step by step in the Ada programming language
You may also check:How to resolve the algorithm Animate a pendulum step by step in the F# programming language
You may also check:How to resolve the algorithm XML/Input step by step in the AWK programming language