AKS test for primes: Difference between revisions
→{{header|F_Sharp|F#}}
(add RPL) |
|||
| (8 intermediate revisions by 7 users not shown) | |||
Line 1,206:
=={{header|Clojure}}==
{{incorrect|Clojure|(x-1)(x-1) is x^2-2x+1 so should the result 2 (-1 2 1) rather be 2 (1 2 1) and similarly for several others}}
The *' function is an arbitrary precision multiplication.
<syntaxhighlight lang="clojure">(defn c
Line 1,480 ⟶ 1,481:
=={{header|Elena}}==
{{trans|C#}}
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 1,495 ⟶ 1,496:
c[i] := 1l;
for (int i := 0
c[1 + i] := 1l;
for (int j := i
c[j] := c[j - 1] - c[j]
};
Line 1,535 ⟶ 1,536:
public program()
{
for (int n := 0
AksTest.coef(n);
Line 1,544 ⟶ 1,545:
console.print("Primes:");
for (int n := 1
if (AksTest.is_prime(n))
{
Line 1,680 ⟶ 1,681:
The primes upto 50: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// N-grams. Nigel Galloway: April 11th., 2024
let fN g=let n,g=g@[0I],0I::g in List.map2(fun n g->n-g) n g
Seq.unfold(fun g->Some(g,fN g))[1I]|>Seq.take 9|>Seq.iteri(fun n g->printfn "%d -> %A" n g); printfn ""
let fG (n::g) l=(n+1I)%l=0I && g|>List.forall(fun n->n%l=0I)
Seq.unfold(fun(n,g)->Some((n,g),(n+1I,fN g)))(0I,[1I])|>Seq.skip 2|>Seq.filter(fun(n,_::g)->fG (List.rev g) n)|>Seq.takeWhile(fun(n,_)->n<100I)|>Seq.iter(fun(n,_)->printf "%A " n); printfn ""
</syntaxhighlight>
{{out}}
<pre>
0 -> [1]
1 -> [1; -1]
2 -> [1; -2; 1]
3 -> [1; -3; 3; -1]
4 -> [1; -4; 6; -4; 1]
5 -> [1; -5; 10; -10; 5; -1]
6 -> [1; -6; 15; -20; 15; -6; 1]
7 -> [1; -7; 21; -35; 35; -21; 7; -1]
8 -> [1; -8; 28; -56; 70; -56; 28; -8; 1]
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
</pre>
Line 3,114 ⟶ 3,138:
primes under 50
{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Function that lists coefficients given the exponent */
pol_to_list(n):=if n=0 then [1] else block(pol:expand((x-1)^n),
makelist(numfactor(part(pol,i)),i,1,length(pol)))$
/* Function to expand the polynomial (x-1)^n */
expansion(n):=block(
coeflist:pol_to_list(n),
makelist(x^(length(%%)-i),i,1,length(%%)),
%%*coeflist,
apply("+",%%))$
/* AKS based predicate function */
aks_primep(n):=if n=1 then false else block(sample:expansion(n)-(x^n-1),
makelist(numfactor(part(sample,i)),i,1,length(sample)),
if not member(false,makelist(integerp(%%[i]/n),i,1,length(%%))) then true)$
/* Test cases */
makelist(expansion(i),i,0,7);
block(
makelist(aks_primep(i),i,1,50),
sublist_indices(%%,lambda([x],x=true)));
</syntaxhighlight>
{{out}}
<pre>
[1,x-1,x^2-2*x+1,x^3-3*x^2+3*x-1,x^4-4*x^3+6*x^2-4*x+1,x^5-5*x^4+10*x^3-10*x^2+5*x-1,x^6-6*x^5+15*x^4-20*x^3+15*x^2-6*x+1,x^7-7*x^6+21*x^5-35*x^4+35*x^3-21*x^2+7*x-1]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
</pre>
=={{header|Nim}}==
Line 4,416 ⟶ 4,472:
|-
|}
=={{header|Quackery}}==
<syntaxhighlight lang="Quackery"> [ dup 0 peek swap
[] 0 rot 0 join
witheach
[ abs tuck +
rot join swap ]
drop
[] swap witheach
[ rot negate
dup dip unrot
* join ]
nip ] is nextcoeffs ( [ --> [ )
[ ' [ 1 ] swap
times nextcoeffs ] is coeffs ( n --> [ )
[ dup 2 < iff
[ drop false ]
done
true swap
dup coeffs
behead drop
-1 split drop
witheach
[ over mod
0 != if
[ dip not
conclude ] ]
drop ] is prime ( n --> b )
[ behead
0 < iff
[ say "-" ]
else sp
dup size
dup 0 = iff
[ 1 echo 2drop ]
done
say "x"
dup 1 = iff
[ 2drop
say " + 1" ]
done
say "^"
echo
witheach
[ dup 0 < iff
[ say " - " ]
else
[ say " + " ]
abs echo
i 0 = if done
say "x"
i 1 = if done
say "^"
i echo ] ] is echocoeffs ( [ --> )
8 times
[ i^ echo
say ": "
i^ coeffs
echocoeffs
cr ]
cr
50 times
[ i^ prime if
[ i^ echo sp ] ]</syntaxhighlight>
{{out}}
<pre>0: 1
1: -x + 1
2: x^2 - 2x + 1
3: -x^3 + 3x^2 - 3x + 1
4: x^4 - 4x^3 + 6x^2 - 4x + 1
5: -x^5 + 5x^4 - 10x^3 + 10x^2 - 5x + 1
6: x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6x + 1
7: -x^7 + 7x^6 - 21x^5 + 35x^4 - 35x^3 + 21x^2 - 7x + 1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 </pre>
=={{header|R}}==
Line 4,770 ⟶ 4,908:
≫ ≫ ‘'''XPM1'''’ STO
≪ DUP SIZE → coeffs size
≪ 0 1 size '''FOR''' j
coeffs j GET 'X' size j - ^ * + '''NEXT'''
≫ ≫ ‘'''SHOWA'''’ STO
≪ DUP '''XPM1''' → p coeffs
≪ 1
Line 4,783 ⟶ 4,926:
end loop
return coeffs
'''SHOWA''' ''( { coeffs } -- 'polynom' )''
loop for each coeff
append jth polynomial term
return polynom
'''PRIM?''' ''( p -- boolean ) ''
Line 4,792 ⟶ 4,940:
{{in}}
<pre>
≪ { } 1 7 FOR n n XPM1 SHOWA + NEXT ≫
≪ { } 2 35 FOR n IF n PRIM? THEN n + END NEXT ≫
</pre>
{{out}}
<pre>
8:
7:
6:
5:
4:
3:
2:
1: { 2 3 5 7 11 13 17 19 23 29 31 }
</pre>
Line 5,797 ⟶ 5,945:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var c = List.filled(p+1, 0)
var r = 1
Line 5,954 ⟶ 6,102:
const std = @import("std");
const assert = std.debug.assert;
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var i: u6 = 0;
while (i < 8) : (i += 1)
try showBinomial(stdout, i);
try stdout.print("\nThe primes upto 50 (via AKS) are: ", .{});
Line 5,968 ⟶ 6,117:
}
fn showBinomial(writer: anytype, n: u6) !void {
const row = binomial(n).?;
var sign: u8 = '+';
var exp = row.len;
try
for (row) |coef| {
try
if (exp != row.len)
try
exp -= 1;
if (coef != 1 or exp == 0)
try
if (exp >= 1) {
try
if (exp > 1)
try
}
sign = if (sign == '+') '-' else '+';
}
try
}
Line 6,008 ⟶ 6,157:
const rmax = 68;
// evaluated and created at compile-time
const pascal = build: {
@setEvalBranchQuota(100_000);
| |||