feat(math): add prime number fns

- add nearestPrime() - add primesUntil() - add tests - update pkg
thi-ng · Dec 12, 2021 · f301256 · f301256
1 parent f832d2f
commit f301256
Show file tree

Hide file tree

Showing 4 changed files with 85 additions and 1 deletion.
diff --git a/packages/math/package.json b/packages/math/package.json
@@ -52,6 +52,7 @@
         "interpolation",
         "interval",
         "math",
+        "prime",
         "quadratic",
         "smooth",
         "solver",
@@ -112,6 +113,9 @@
         "./prec": {
             "import": "./prec.js"
         },
+        "./prime": {
+            "import": "./prime.js"
+        },
         "./ratio": {
             "import": "./ratio.js"
         },

diff --git a/packages/math/src/index.ts b/packages/math/src/index.ts
@@ -11,6 +11,7 @@ export * from "./libc.js";
 export * from "./min-error.js";
 export * from "./mix.js";
 export * from "./prec.js";
+export * from "./prime.js";
 export * from "./ratio.js";
 export * from "./safe-div.js";
 export * from "./solve.js";

diff --git a/packages/math/src/prime.ts b/packages/math/src/prime.ts
@@ -0,0 +1,53 @@
+/**
+ * Returns iterator of all prime numbers ≤ given `x` using Sieve of
+ * Eratosthenes.
+ *
+ * @remarks
+ * Reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+ *
+ * @param x
+ */
+export function* primesUntil(x: number) {
+    if (x < 1) return;
+    yield 1;
+    const sieve: boolean[] = [];
+    const max = Math.sqrt(x) | 0;
+    for (let i = 2; i <= x; i++) {
+        if (!sieve[i]) {
+            yield i;
+            __updateSieve(sieve, i, x, max);
+        }
+    }
+}
+
+/**
+ * Returns largest prime number ≤ given `x` using Sieve of Eratosthenes. Returns
+ * -1 if x < 1.
+ *
+ * @remarks
+ * Reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+ *
+ * @param x
+ */
+export const nearestPrime = (x: number) => {
+    if (x < 1) return -1;
+    let prime = 1;
+    const sieve: boolean[] = [];
+    const max = Math.sqrt(x) | 0;
+    for (let i = 2; i <= x; i++) {
+        if (!sieve[i]) {
+            prime = i;
+            __updateSieve(sieve, i, x, max);
+        }
+    }
+    return prime;
+};
+
+/**
+ * @internal
+ */
+const __updateSieve = (sieve: boolean[], i: number, x: number, max: number) => {
+    if (i <= max) {
+        for (let j = i * i; j <= x; j += i) sieve[j] = true;
+    }
+};
diff --git a/packages/math/test/index.ts b/packages/math/test/index.ts
@@ -1,6 +1,12 @@
 import { group } from "@thi.ng/testament";
 import * as assert from "assert";
-import { fmod, mod, remainder } from "../src/index.js"
+import {
+    fmod,
+    mod,
+    nearestPrime,
+    primesUntil,
+    remainder,
+} from "../src/index.js";
 
 group("math", {
     fmod: () => {
@@ -19,4 +25,24 @@ group("math", {
         assert.strictEqual(remainder(3.75, 2), -0.25);
         assert.strictEqual(remainder(-3.75, 2), 0.25);
     },
+
+    primes: () => {
+        assert.deepStrictEqual([...primesUntil(0)], []);
+        assert.deepStrictEqual([...primesUntil(1)], [1]);
+        assert.deepStrictEqual(
+            [...primesUntil(100)],
+            [
+                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,
+            ]
+        );
+        assert.strictEqual(nearestPrime(-2), -1);
+        assert.strictEqual(nearestPrime(0), -1);
+        assert.strictEqual(nearestPrime(1), 1);
+        assert.strictEqual(nearestPrime(2), 2);
+        assert.strictEqual(nearestPrime(4), 3);
+        assert.strictEqual(nearestPrime(8), 7);
+        assert.strictEqual(nearestPrime(16), 13);
+        assert.strictEqual(nearestPrime(1024), 1021);
+    },
 });