2
Rust, \$n = 15\$
use std::collections::VecDeque;
fn miller(n: u64, mut b: u64) -> bool {
let s = (n - 1).trailing_zeros();
let mut t = n - 1 >> s;
b %= n;
let mut a = b;
while t != 1 {
b = b * b % n;
t >>= 1;
if t & 1 != 0 {
a = a * b % n;
}
}
if a == 1 || a == n - 1 ...
1
C++ (clang), \$n=14\$
#include <iostream>
#include <cmath>
#include <chrono>
#include <iomanip>
template <typename I>
bool isPrime(I n)
{
if (n < 2) {
return false;
}
if (n == 2 || n == 3) {
return true;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
I srt = std::sqrt(n)...
1
JavaScript (Node.js), \$n=15\$
This is essentially just a port of the example implementation, with an optimized modular exponentiation and a cache for odd composite numbers.
Further optimized by merging powMod() and miller(), as Anders Kaseorg first did.
function miller(n, b) {
let s = 31 - Math.clz32(n - 1 & 1 - n);
let t = n - 1 >> s;
...
1
05AB1E, 18 17 bytes
ΘIg5›ITLBpàI1K`O_
-1 byte and bug-fix thanks to @Grimmy.
Outputs 1/0 for truthy/falsey respectively.
Try it online or verify all test cases or verify the first 40 binary numbers and 100 regular numbers.
(Now longer) 18 bytes alternative:
46bICèIт@Ig6‹PITм+
Outputs 1 for truthy and a non-1 integer for falsey (note: only 1 is truthy ...
Only top voted, non community-wiki answers of a minimum length are eligible
