AKS test for primes: Difference between revisions
→{{header|zkl}}
(solving the task with lambdatalk) |
|||
Line 4,888:
AKS_test_for_primes()</lang>
=={{header|Zig}}==
Uses Zig's compile-time interpreter to create Pascal's triangle at compile-time.
<lang Zig>
const std = @import("std");
const assert = std.debug.assert;
const stdout = std.io.getStdOut().outStream();
pub fn main() !void {
var i: u6 = 0;
while (i < 8) : (i += 1)
try showBinomial(i);
try stdout.print("\nThe primes upto 50 (via AKS) are: ", .{});
i = 2;
while (i <= 50) : (i += 1) if (aksPrime(i))
try stdout.print("{} ", .{i});
try stdout.print("\n", .{});
}
fn showBinomial(n: u6) !void {
const row = binomial(n).?;
var sign: u8 = '+';
var exp = row.len;
try stdout.print("(x - 1)^{} =", .{n});
for (row) |coef| {
try stdout.print(" ", .{});
if (exp != row.len)
try stdout.print("{c} ", .{sign});
exp -= 1;
if (coef != 1 or exp == 0)
try stdout.print("{}", .{coef});
if (exp >= 1) {
try stdout.print("x", .{});
if (exp > 1)
try stdout.print("^{}", .{exp});
}
sign = if (sign == '+') '-' else '+';
}
try stdout.print("\n", .{});
}
fn aksPrime(n: u6) bool {
return for (binomial(n).?) |coef| {
if (coef > 1 and coef % n != 0)
break false;
} else true;
}
pub fn binomial(n: u32) ?[]const u64 {
if (n >= rmax)
return null
else {
const k = n * (n + 1) / 2;
return pascal[k .. k + n + 1];
}
}
const rmax = 68;
const pascal = build: {
@setEvalBranchQuota(100_000);
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined;
coefficients[0] = 1;
var j: u32 = 0;
var k: u32 = 1;
var n: u32 = 1;
while (n < rmax) : (n += 1) {
var prev = coefficients[j .. j + n];
var next = coefficients[k .. k + n + 1];
next[0] = 1;
var i: u32 = 1;
while (i < n) : (i += 1)
next[i] = prev[i] + prev[i - 1];
next[i] = 1;
j = k;
k += n + 1;
}
break :build coefficients;
};
</lang>
{{Out}}
<pre>
$ zig run aks.zig
(x - 1)^0 = 1
(x - 1)^1 = x - 1
(x - 1)^2 = x^2 - 2x + 1
(x - 1)^3 = x^3 - 3x^2 + 3x - 1
(x - 1)^4 = x^4 - 4x^3 + 6x^2 - 4x + 1
(x - 1)^5 = x^5 - 5x^4 + 10x^3 - 10x^2 + 5x - 1
(x - 1)^6 = x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6x + 1
(x - 1)^7 = x^7 - 7x^6 + 21x^5 - 35x^4 + 35x^3 - 21x^2 + 7x - 1
The primes upto 50 (via AKS) are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
</pre>
=={{header|zkl}}==
{{trans|Python}}
| |||