You are going to create a List in Javascript using JSFiddle. You will then fill

Question

You are going to create a List in Javascript using JSFiddle. You will then fill it with numbers consecutively numbered from 2 to n where n is entered by the user.

Create a second List - this one should be a Queue - it is empty.

Once you have the first List filled we are going to use a technique called Sieve of Eratosthenes which uses first queue to fill the second queue. You will need to look at the algorithm for this https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here is the simple method to do this - L1 is the first list, Q1 is the Queue.

1. Go to 1st element in L1 (which will be 2).

2. Because it exists - Push this into Q1 and remove it from L1

3. Iterate through each element of L1 and if the value is divisible by 2 remove it.

4. When done go back to the beginning of the list (the value will be 3 the second time around)

5. Print Iteration 1, Value of L1 (all elements) and Q1 (all elements)

6. Repeat steps 2-5 with this new element - repeat until L1 is empty.

Sample output with input 10

Iteration 0: L1 = 2 3 4 5 6 7 8 9 10, Q1 = ,

Iteration 1: L1 = 3 5 7 9, Q1 = 2

Iteration 2: L1 = 5 7, Q1 = 2 3

Iteration 3: L1 = 7, Q1 = 2 3 5

Iteration 4: L1 = , Q1 = 2 3 5 7

Please include the complete code and screenshot of the fiddle if able.

Explanation / Answer

var tm = Date.now();
var db = new alasql.Database();
db.exec('CREATE TABLE primes (prime INT)');
function primecheck (number)
{
var isprime = true;
if (number%10 == 1 || number%10 == 3 || number%10 == 7 || number%10 == 9)
{
db.exec('SELECT * FROM primes', [], function (result)
{
for (var i = 1; i < result.length; i++)
{
if (number%result[i].prime == 0)
{
isprime = false;
break;
}
}
if (isprime)
{
db.exec('INSERT INTO primes (prime) VALUES ('+number+')');
}
return isprime;
});
} else
{
isprime = false;
return isprime;
}
}
var maxnum = 1000;
for(var i=1; i<maxnum;i++)
{
primecheck(i);
};
var cnt = db.exec('SELECT COUNT(prime) AS cnt FROM primes GROUP BY prime')[0].cnt;
var res = db.exec('SELECT * FROM primes');
var s = '<p>There are '+cnt+' prime numbers less than '+maxnum+': <br> '+res.map(function(p){return p.prime}).join(', ')+'</p><p>Time '+(Date.now()-tm)+' ms </p>';
document.getElementById('res').innerHTML = s;

or

function sieve(max) {
var D = [], primes = [];
for (var q=2; q<max; q++) {
  if (D[q]) {
   for (var i=0; i<D[q].length; i++) {
     var p = D[q][i];
     if (D[p+q]) D[p+q].push(p);
     else D[p+q]=[p];
   }
   delete D[q];
  } else {
   primes.push(q);
   if (q*q<max) D[q*q]=[q];
  }
}
return primes;
}
sieve(100)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.