素数を調べるプログラム

prime-number-4.js

module.exports.primes = [2, 3];
module.exports.nextCheck = 5;

module.exports.isPrime = (n) => {
    if (n < this.nextCheck)
        return this.primes.includes(n);

    return this.isPrime2(n);
};

module.exports.isPrime2 = (n) => {
    return this.isPrime4(n);
};

module.exports.isPrime3 = (n) => {
    if (n < 2 || n % 2 === 0) return false;
    else if (n === 2) return true;

    const sqrtNum = Math.sqrt(n);
    for (let i = 3; i <= sqrtNum; i += 2)
        if (n % i === 0)
            return false;

    return true;
};

module.exports.isPrime4 = (n) => {
    if (n < 2 || n % 2 === 0 || n % 3 === 0) return false;
    else if (n === 2) return true;

    const sqrtNum = Math.sqrt(n);
    for (let i = 5; i <= sqrtNum; i += 6)
        if (n % i === 0 || n % (i + 2) === 0)
            return false;

    return true;
};

module.exports.checkPrime4 = (end) => {
    //this.a = 0;
    let i;
    for (i = this.nextCheck; i <= end; i += 6) {
        //this.a++;
        if (this.isPrime2(i))
            this.primes.push(i);
        if (this.isPrime2(i + 2))
            this.primes.push(i + 2);
    }
    this.nextCheck = i;
};

prime-number-5.js

// Fastest
// Sieve of Eratosthenes
module.exports.primes = [];

module.exports.checkPrime5 = (end) => {
    //this.b = this.a = 0;
    let i, j;
    let l = Array(end - 1);
    for (i = 2; i <= end; i++) {
        //this.a++;
        if (l[i - 2] === undefined) {
            this.primes.push(i);
            for (j = i + i; j <= end; j += i) {
                //this.b++;
                l[j - 2] = false;
            }
        }
    }
};

prime-number-slow.js

module.exports.primes = [2];
module.exports.nextCheck = 3;

module.exports.checkPrime1 = (end) => {
    //this.b = this.a = 0;
    let isPrime, i;
    for (i = this.nextCheck; i <= end; i += 2) {
        //this.a++;
        isPrime = true;
        for (let i1 = 0; i1 < this.primes.length; i1++) {
            //this.b++;
            if (i % this.primes[i1] === 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            this.primes.push(i);
    }
    this.nextCheck = i;
};

prime-number.js

module.exports.primes = [2];
module.exports.nextCheck = 3;
module.exports.pattern1 = [1];
module.exports.pattern1SizeA = 2;
module.exports.pattern1SizeB = 2; // A003418 - OEIS
module.exports.pattern1i = 0;
module.exports.pattern1ps = 1;
module.exports.pattern1pe = 1;

module.exports.checkPrime2 = (end) => {
    //this.g = this.f = this.e = this.d = this.c = this.b = this.a = 0;
    let isPrime, i1, i2, i3, j;
    let i = this.nextCheck;
    while (i <= end) {
        //this.a++;
        isPrime = true;
        for (i1 = this.pattern1ps; this.primes[i1] <= this.pattern1pe; i1++) {
            //this.b++;
            if (i % this.primes[i1] === 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            this.primes.push(i);

        j = true;
        for (i1 = this.pattern1SizeA + 1; i1 <= i; i1++) {
            //this.c++;
            if ((i - 1) % i1 !== 0)
                break;
        }
        if (i1 - 1 > this.pattern1SizeA)
            for (i2 = this.pattern1SizeA; i2 >= 2; i2--) {
                //this.d++;
                if ((i - 1) % i2 !== 0)
                    break;
                else if (i2 === 2) {
                    j = false;
                    break;
                }
            }

        if (j) {
            i3 = i - this.pattern1[i1 = this.pattern1i];
            this.pattern1i = (this.pattern1i + 1) % this.pattern1.length;
            if (this.pattern1i <= i1)
                i3 += this.pattern1SizeB;
        } else {
            this.pattern1SizeA = i1 - 1;
            this.pattern1SizeB = i - 1;
            i3 = this.pattern1SizeB;
            this.pattern1i = 1;

            this.pattern1 = [1]; // 1-12 > 1, 5, 7, 11
            for (i1 = this.pattern1SizeA + 1; i1 < this.pattern1SizeB - this.pattern1SizeA; i1++) {
                //this.e++;
                for (i2 = 2; i2 <= this.pattern1SizeA; i2++) {
                    //this.f++;
                    if (i1 % i2 === 0)
                        break;
                }
                if (i2 > this.pattern1SizeA)
                    this.pattern1.push(i1);
            }
            this.pattern1.push(this.pattern1SizeB - 1);

            for (i1 = this.pattern1ps; i1 < this.primes.length; i1++) {
                //this.g++;
                if (this.primes[i1] <= this.pattern1SizeA)
                    this.pattern1ps = i1 + 1;
                else
                    break;
            }
        }

        i = i3 + this.pattern1[this.pattern1i];
        this.pattern1pe = Math.sqrt(i);
    }
    this.nextCheck = i;
};

module.exports.checkPrime3 = (end) => {
    //this.h = this.g = this.f = this.e = this.d = this.c = this.b = this.a = 0;
    let isPrime, i1, i2, i3, j;
    let i = this.nextCheck;
    while (i <= end) {
        //this.a++;
        isPrime = true;
        for (i1 = this.pattern1ps; this.primes[i1] <= this.pattern1pe; i1++) {
            //this.b++;
            if (i % this.primes[i1] === 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            this.primes.push(i);

        j = true;
        for (i1 = this.pattern1SizeA + 1; i1 <= i; i1++) {
            //this.c++;
            if ((i - 1) % i1 !== 0)
                break;
        }
        if (i1 - 1 > this.pattern1SizeA)
            for (i2 = this.pattern1SizeA; i2 >= 2; i2--) {
                //this.d++;
                if ((i - 1) % i2 !== 0)
                    break;
                else if (i2 === 2) {
                    j = false;
                    break;
                }
            }

        if (j) {
            i3 = i - this.pattern1[i1 = this.pattern1i];
            this.pattern1i = (this.pattern1i + 1) % this.pattern1.length;
            if (this.pattern1i <= i1)
                i3 += this.pattern1SizeB;
        } else {
            this.pattern1SizeA = i1 - 1;
            this.pattern1SizeB = i - 1;
            i3 = this.pattern1SizeB;
            this.pattern1i = 1;

            this.pattern1 = [1]; // 1-12 > 1, 5, 7, 11
            // First half
            for (i1 = this.pattern1SizeA + 1; i1 < this.pattern1SizeB >>> 1; i1++) {
                //this.e++;
                for (i2 = 2; i2 <= this.pattern1SizeA; i2++) {
                    //this.f++;
                    if (i1 % i2 === 0)
                        break;
                }
                if (i2 > this.pattern1SizeA)
                    this.pattern1.push(i1);
            }
            // Second half
            for (i1 = this.pattern1.length - 1; i1 >= 0; i1--) {
                //this.g++;
                this.pattern1.push(this.pattern1SizeB - this.pattern1[i1]);
            }

            for (i1 = this.pattern1ps; i1 < this.primes.length; i1++) {
                //this.h++;
                if (this.primes[i1] <= this.pattern1SizeA)
                    this.pattern1ps = i1 + 1;
                else
                    break;
            }
        }

        i = i3 + this.pattern1[this.pattern1i];
        this.pattern1pe = Math.sqrt(i);
    }
    this.nextCheck = i;
};

test.js

const { performance } = require('perf_hooks');
const prime = require('./prime-number.js');

var t = performance.now();
//prime.checkPrime2(12); // 5
//prime.checkPrime2(60); // 17
//prime.checkPrime2(420); // 81
//prime.checkPrime2(840); // 146
prime.checkPrime2(200000); // 17984
console.log(Math.floor(performance.now() - t) + " ms.");
//console.log(prime);
console.log(prime.primes.length);

// -200k
// checkPrime1: 2101 ms
// checkPrime2: 83 ms
// checkPrime3: 87 ms
// checkPrime4: 66 ms
// checkPrime5: 46 ms