Skip to content

Instantly share code, notes, and snippets.

@boris-spas
Created Oct 15, 2021
Embed
What would you like to do?
// Naive prime calculator
function isPrime(x) {
for (i = 2; i < x; i++) {
if (x % i == 0) {
return false
}
}
return true
}
function findPrime(i) {
prime=1;
do {
prime=prime + 1;
if (isPrime(prime)) {
i--;
}
} while(i > 0);
return prime
}
// Prime number calculator based on the Sieve of Eratosthenes algorithm.
class AcceptFilter {
accept(n) {
return true
}
}
class DivisibleByFilter {
constructor(number, next) {
this.number = number;
this.next = next;
}
accept(n) {
var filter = this;
// if (filter != null) {
while (filter != null) {
if (n % filter.number === 0) {
return false;
}
// return filter.next.accept(n);
filter = filter.next;
}
return true;
}
}
class Primes {
constructor() {
this.number = 2;
this.filter = new AcceptFilter();
}
next() {
while (!this.filter.accept(this.number)) {
this.number++;
}
this.filter = new DivisibleByFilter(this.number, this.filter);
return this.number;
}
}
// Verify results are the same
var primes = new Primes();
for (let i = 1; i <= 1000; i++) {
sievePrive = primes.next()
naivePrime = findPrime(i)
if (naivePrime != sievePrive || !isPrime(sievePrive)) {
throw "Error!" + i
}
}
console.log('OK')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment