AKS test for primes: Difference between revisions

{{trans|Python}}

 

V ex = [BigInt(1)]

L(i) 0 .< p

 

=={{header|8th}}==

with: a

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */

/* program AKS64.s */

 

=={{header|Ada}}==

 

procedure Test_For_Primes is

The code below uses Algol 68 Genie which provides arbitrary precision arithmetic for LONG LONG modes.

 

BEGIN

COMMENT

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}

/* ARM assembly Raspberry PI or android 32 bits */

/* program AKS.s */

=={{header|AutoHotkey}}==

{{works with|AutoHotkey L}}

; Function modified from http://rosettacode.org/wiki/Pascal%27s_triangle#AutoHotkey

pascalstriangle(n=8) ; n rows of Pascal's triangle

 

The primality test uses a pattern that looks for a fractional factor. If such a factor is found, the test fails. Otherwise it succeeds.

& (expandx-1P=.forceExpansion$((x+-1)^!arg))

& ( isPrime

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47</pre>

The AKS test kan be written more concisely than the task describes. This prints the primes between 980 and 1000:

& 980:?n

& whl

 

=={{header|C}}==

#include <stdlib.h>

 

=={{header|C sharp|C#}}==

{{trans|C}}

using System;

public class AksTest

=={{header|C++}}==

{{trans|Pascal}}

#include <iomanip>

#include <iostream>

=={{header|Clojure}}==

The *' function is an arbitrary precision multiplication.

"kth coefficient of (x - 1)^n"

[n k]

 

=={{header|CoffeeScript}}==

a = []

return () ->

 

=={{header|Common Lisp}}==

(cond

((= p 0) #(1))

=={{header|Crystal}}==

{{trans|Ruby}}

p.times.reduce([1]) do |ex, _|

([0_i64] + ex).zip(ex + [0]).map { |x, y| x - y }

=={{header|D}}==

{{trans|Python}}

 

BigInt[] expandX1(in uint p) pure /*nothrow*/ {

=={{header|EchoLisp}}==

We use the math.lib library and the poly functions to compute and display the required polynomials. A polynomial P(x) = a0 +a1*x + .. an*x^n is a list of coefficients (a0 a1 .... an).

(lib 'math.lib)

;; 1 - x^p : P = (1 0 0 0 ... 0 -1)

</syntaxhighlight>

{{Output}}

(show-them 13) →

p 1 x -1

{{trans|C#}}

ELENA 4.x :

singleton AksTest

=={{header|Elixir}}==

{{trans|Erlang}}

def iterate(f, x), do: fn -> [x | iterate(f, f.(x))] end

The Erlang io module can print out lists of characters with any level of nesting as a flat string. (e.g. ["Er", ["la", ["n"]], "g"] prints as "Erlang") which is useful when constructing the strings to print out for the binomial expansions. The program also shows how lazy lists can be implemented in Erlang.

 

 

-import(lists, [all/2, seq/2, zip/2]).

 

=={{header|Factor}}==

math.polynomials prettyprint sequences ;

IN: rosetta-code.aks-test

 

=={{header|Forth}}==

1 swap 1+ dup 1 ?do over over i - i */ negate swap loop drop ;

 

 

=={{header|Fortran}}==

program aks

implicit none

 

=={{header|FreeBASIC}}==

'UPPER LIMIT OF FREEBASIC ULONGINT GETS PRIMES UP TO 70

Sub string_split(s_in As String,char As String,result() As String)

 

=={{header|Go}}==

 

import "fmt"

 

=={{header|Haskell}}==

 

 

 

=={{header|Idris}}==

 

-- Computes Binomial Coefficients

=={{header|J}}==

 

testAKS =: 0 *./ .= ] | binomialExpansion NB. 3) Use that function to create another which determines whether p is prime using AKS.</syntaxhighlight>

 

+-++--+----+-------+-----------+---------------+------------------+

|0||_2|_3 3|_4 6 _4|_5 10 _10 5|_6 15 _20 15 _6|_7 21 _35 35 _21 7|

 

{{trans|C}}

private static final long[] c = new long[64];

 

=={{header|JavaScript}}==

{{trans|CoffeeScript}}

 

pascal = function() {

The primes upto 50 are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47</pre>

Reviewed (ES6):

var cs = []; if (n) while (n--) coef(); return coef

function coef() {

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

{{trans|C}}

for (var c=[1], i=0; i<n; c[0]=-c[0], i+=1) {

c[i+1]=1; for (var j=i; j; j-=1) c[j] = c[j-1]-c[j]

easily be adapted to use a BigInt library such as the one at

https://github.com/joelpurra/jq-bigint

# Input: an OptPascal array

# Output: the next OptPascal array (obtained by adding adjacent items,

 

'''Task 1:''' "A method to generate the coefficients of (x-1)^p"

def alternate_signs: . as $in

| reduce range(0; length) as $i ([]; . + [$in[$i] * (if $i % 2 == 0 then 1 else -1 end )]);

'''Task 2:''' "Show here the polynomial expansions of (x − 1)^p for p in the range 0 to at least 7, inclusive."

{{out}}

Coefficients for (x - 1)^1: [1,-1]

Coefficients for (x - 1)^2: [1,-2,1]

 

For brevity, we show here only the relatively efficient solution based on optpascal/0:

. as $N

| if . < 2 then false

 

'''Task 4:''' "Use your AKS test to generate a list of all primes under 35."

{{out}}

3

5

 

'''Task 5:''' "As a stretch goal, generate all primes under 50."

{{out}}

 

=={{header|Julia}}==

'''Task 1'''

 

function polycoefs(n::Int64)

pc = typeof(n)[]

'''Task 2'''

 

 

function stringpoly(n::Int64)

'''Task 3'''

 

function isaksprime(n::Int64)

if n < 2

'''Task 4'''

 

println("<math>")

println("\\begin{array}{lcl}")

 

=={{header|Kotlin}}==

 

fun binomial(n: Int, k: Int): Long = when {

</pre>

=={{header|Lua}}==

local function coefs(n)

local list = {[0]=1}

 

=={{header|Lambdatalk}}==

{require lib_BN} // for big numbers

 

{{trans|Pascal}}

{{works with|Just BASIC|any}}

global pasTriMax

pasTriMax = 61

=={{header|Maple}}==

Maple handles algebraic manipulation of polynomials natively.

1

 

</syntaxhighlight>

To implement the primality test, we write the following procedure that uses the (built-in) polynomial expansion to generate a list of coefficients of the expanded polynomial.

Use <code>polc</code> to implement <code>prime?</code> which does the primality test.

Of course, rather than calling <code>polc</code>, we can inline it, just for the sake of making the whole thing a one-liner (while adding argument type-checking for good measure):

This agrees with the built-in primality test <code>isprime</code>:

true

</syntaxhighlight>

Use <code>prime?</code> with the built-in Maple <code>select</code> procedure to pick off the primes up to 50:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

</syntaxhighlight>

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Algebraic manipulation is built into Mathematica, so there's no need to create a function to do (x-1)^p

(x - 1)^( Range[0, 7]) // Expand // TableForm

Print["primes under 50"]

 

=={{header|Nim}}==

from math import binom

import strutils

=={{header|Objeck}}==

{{trans|Java}}

@c : static : Int[];

{{trans|Clojure}}

Uses [http://github.com/c-cube/gen gen] library for lazy streams and [https://forge.ocamlcore.org/projects/zarith zarith] for arbitrarily sized integers. Runs as is through the [https://github.com/diml/utop utop] REPL.

#require "zarith"

open Z

 

=={{header|Oforth}}==

 

: nextCoef( prev -- [] )

 

=={{header|PARI/GP}}==

vector(8,n,getPoly(n-1))

AKS_slow(n)=my(P=getPoly(n));for(i=1,n-1,if(polcoeff(P,i)%n,return(0))); 1;

=={{header|Pascal}}==

{{works with|Free Pascal}}

const

pasTriMax = 61;

 

=={{header|Perl}}==

use warnings;

# Select one of these lines. Math::BigInt is in core, but quite slow.

 

{{libheader|ntheory}}

# Uncomment next line to see the r and s values used. Set to 2 for more detail.

# prime_set_config(verbose => 1);

 

=={{header|Phix}}==

<span style="color: #000080;font-style:italic;">-- demo/rosetta/AKSprimes.exw

-- Does not work for primes above 53, which is actually beyond the original task anyway.

 

=={{header|Picat}}==

pascal([]) = [1].

pascal(L) = [1|sum_adj(L)].

 

=={{header|PicoLisp}}==

(let D 1

(make

 

=={{header|PL/I}}==

AKS: procedure options (main, reorder); /* 16 September 2015, derived from Fortran */

 

connection can be expressed directly in Prolog by the following prime number

generator:

prime(P) :-

pascal([1,P|Xs]),

 

===Pascal Triangle Generator===

% To generate the n-th row of a Pascal triangle

% pascal(+N, Row)

Solutions with output from SWI-Prolog:

 

%%% Task 1: "A method to generate the coefficients of (1-X)^p"

 

</pre>

 

%%% Task 3. Use the previous function in creating [sic]

%%% another function that when given p returns whether p is prime

recomputation):

 

prime(N) :- optpascal([1,N|Xs]), forall( member(X,Xs), 0 is X mod N).

</syntaxhighlight>

 

%%% Task 4. Use your AKS test to generate a list of all primes under 35.

 

 

It would be possible to go further and expand (a + b)^n and collect terms, but that turns out to be rather difficult because terms have to be reordered into a canonical form first -- for example, an expansion can produce both j*a*b and k*b*a, and these terms would have to be reordered to get (j+k)*a*b.

main :- task1(8), nl, task2(50), halt.

 

 

=={{header|PureBasic}}==

Define vzr.b = -1, vzc.b = ~vzr, nMAX.i = 10, n.i , k.i

 

=={{header|Python}}==

 

# This version uses a generator and thus less computations

c =1

return True</syntaxhighlight>

or equivalently:

if p==2:return True

c=1

return True</syntaxhighlight>

alternatively:

ex = [1]

for i in range(p):

Using a wikitable and math features with the following additional code produces better formatted polynomial output:

 

{| class="wikitable" style="text-align:left;"

|+ Polynomial Expansions and AKS prime test

 

i<-2:p-1

l<-unique(factorial(p) / (factorial(p-i) * factorial(i)))

With copious use of the math/number-theory library...

 

(require math/number-theory)

 

The <tt>polyprime</tt> function pretty much reads like the original description. Is it "so" that the p'th expansion's coefficients are all divisible by p? The <tt>.[1 ..^ */2]</tt> slice is done simply to weed out divisions by 1 or by factors we've already tested (since the coefficients are symmetrical in terms of divisibility). If we wanted to write <tt>polyprime</tt> even more idiomatically, we could have made it another infinite constant list that is just a mapping of the first list, but we decided that would just be showing off. <tt>:-)</tt>

 

 

sub polyprime($p where 2..*) { so expansions[$p].[1 ..^ */2].all %% $p }

=={{header|REXX}}==

===version 1===

* 09.02.2014 Walter Pachl

* 22.02.2014 WP fix 'accounting' problem (courtesy GS)

 

The program determines programmatically the required number of decimal digits (precision) for the large coefficients.

parse arg Z . /*obtain optional argument from the CL.*/

if Z=='' | Z=="," then Z= 200 /*Not specified? Then use the default.*/

Using the `polynomial` Rubygem, this can be written directly from the definition in the description:

 

 

def x_minus_1_to_the(p)

Or without the dependency:

 

p.times.inject([1]) do |ex, _|

([0] + ex).zip(ex + [0]).map { |x,y| x - y }

 

=={{header|Rust}}==

let mut coefficients = vec![0i64; k + 1];

coefficients[0] = 1;

An alternative version which computes the coefficients in a more functional but less efficient way.

 

fn aks_coefficients(k: usize) -> Vec<i64> {

if k == 0 {

 

=={{header|Scala}}==

 

val pascal = (( Vector(Vector(BigInt(1))) /: (1 to 50)) { (rows, i) =>

=={{header|Scheme}}==

 

;; implement mod m arithmetic with polnomials in x

;; as lists of coefficients, x^0 first.

=={{header|Scilab}}==

 

clear

xdel(winsid())

 

=={{header|Seed7}}==

 

const func array integer: expand_x_1 (in integer: p) is func

=={{header|Sidef}}==

{{trans|Perl}}

p >= 2 || return false

for i in (1 .. p>>1) {

Using the [https://ideas.repec.org/c/boc/bocode/s455001.html moremata] library to print the polynomial coefficients. They are in decreasing degree order. To install moremata, type '''ssc install moremata''' in Stata. Since Stata is using double precision floating-point instead of 32 bit integers, the polynomials are exact up to p=54.

 

function pol(n) {

a=J(1,n+1,1)

 

=={{header|Swift}}==

var result = [Int](count : n+1, repeatedValue : 0)

=={{header|Tcl}}==

A recursive method with memorization would be more efficient, but this is sufficient for small-scale work.

set clist 1

for {set i 0} {$i < $p} {incr i} {

=={{header|Transd}}==

{{trans|Python}}

#lang transd

 

 

=={{header|uBasic/4tH}}==

Push n : Gosub _coef : Gosub _drop

Print "(x-1)^";n;" = ";

=={{header|VBA}}==

{{trans|Phix}}

'-- Does not work for primes above 97, which is actually beyond the original task anyway.

'-- Translated from the C version, just about everything is (working) out-by-1, what fun.

=={{header|Vlang}}==

{{trans|go}}

mut c := []i64{len: p+1}

mut r := i64(1)

=={{header|Wren}}==

{{trans|Go}}

var c = List.filled(p+1, 0)

var r = 1

=={{header|Yabasic}}==

{{trans|Phix}}

// Translated from the C version, just about everything is (working) out-by-1, what fun.

 

=={{header|Zig}}==

Uses Zig's compile-time interpreter to create Pascal's triangle at compile-time.

const std = @import("std");

const assert = std.debug.assert;

=={{header|zkl}}==

{{trans|Python}}

fcn expand_x_1(p){

ex := L(BN(1));