30:T650, { const form = html``; const controller = { stop: false, pause: false }; // start form.button[0].onclick = event => { event.preventDefault(); // Don’t submit the form. d3.select("#start").attr("disabled", "true"); d3.select("#reset").attr("disabled", "true"); d3.select("#stop").attr("disabled", null); d3.select("#pause").attr("disabled", null); reset(); controller.stop = false; controller.pause = false; run(200, 50, controller); }; // reset form.button[1].onclick = event => { event.preventDefault(); // Don’t submit the form. reset(); }; // stop form.button[2].onclick = event => { event.preventDefault(); // Don’t submit the form. controller.stop = true; controller.pause = false; d3.select("#pause").html( "pause"); }; // pause form.button[3].onclick = event => { event.preventDefault(); // Don’t submit the form. controller.pause = !controller.pause; d3.select("#pause").html(controller.pause ? "continue" : "pause"); }; // run first time without delays run(0,0); d3.select("#stop").attr("disabled", true); d3.select("#pause").attr("disabled", true); return form; }31:T11c1,{ const svg = d3.select(DOM.svg(width, H)); svg.classed("graph", true); // // Image // const imgX = width / 2 - 20; const imgY = 15 + (H - imgWidth) / 2; svg.append("image") .attr("xlink:href","https://upload.wikimedia.org/wikipedia/commons/b/b3/Eratosthene.01.png") .attr("x", imgX) .attr("y", imgY) .attr("opacity", 0.3) .attr("width", imgWidth) .attr("height", imgWidth); svg.append("text") .style("fill", c1) .style("text-anchor", "middle") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "normal" ) .style('font-size', "2.5em") .attr("dy", "0.5em") .attr("x", imgX + imgWidth/2) .attr("y", imgY + imgWidth/3) .text(`N=${N}`); svg.append("text") .attr("id", "status") .style("fill", c1) .style("opacity", 0.8) .style("text-anchor", "start") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "normal" ) .style('font-size', "0.9em") .attr("dy", "1em") .attr("x", 20) .attr("y", 6) .text(`step 1`); const eratos = svg.append("text") .style("fill", c1) .style("opacity", 0.8) .style("text-anchor", "middle") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "normal" ) .style('font-size', "0.7em") .attr("x", imgX + imgWidth / 2) .attr("y", imgY + imgWidth / 4) .text(`Eratosthenes of Cyrene`); // // Legend // const w = 0.6 * cellSize; const g = svg.append("g") .attr("transform", `translate(${imgX + imgWidth/3},${imgWidth/2 + 0.1 * imgWidth})`) .selectAll("g.legend") .data(legendData) .enter() .append("g") .classed("legend", true) .attr("transform", (d,i) => `translate(0,${i * (w+1) })`); g.append("rect") .attr("width", w) .attr("height", w) .style("fill", d => d.color) .style("fill-opacity", d => d.opacity); const t = g.append("text") .style("fill", "white") .style("text-anchor", "middle") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "bold" ) .style('font-size', "0.7em") .attr("x", w/2) .attr("y", w/2) .attr("dy", "0.3em"); t.append("tspan") .text(d => d.val); t.append("tspan") .style("fill", "#1F4057") .style("text-anchor", "start") .style("font-weight", "normal" ) .attr("x", w + 4) .text(d => d.label); // // Draw Initial Grid // const cell = svg.selectAll("g.cell") .data(gridata) .enter() .append("g") .classed("cell", true) .attr("id", d => `_${d.number}`) .attr("transform", d => `translate(${d.col * (cellSize + padding)},${20 + d.row * (cellSize + padding)})`); cell.append("rect") .attr("width", cellSize) .attr("height", cellSize) .attr("x", -cellSize/2) .attr("y", -cellSize/2) .style("fill", c5) .style("stroke", "white") .style("stroke-width", 0); cell.append("text") .style("fill", "white") .style("text-anchor", "middle") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "bold" ) .attr("dy", "0.5em") .style('font-size', "1em") .text(d => d.number); let x0 = imgX + imgWidth / 2; let y0 = imgY + imgWidth / 2; let r0 = 0.94 * imgWidth / 2; let cell2 = svg.selectAll("g.cell2") .data(gridata) .enter() .append("g") .classed("cell2", true) .attr("id", d => `c_${d.number}`) .attr("transform", (d, i) => { let x = x0 + r0 * Math.cos(d.angle); let y = y0 + r0 * Math.sin(d.angle); return `translate(${x},${y})`; }); cell2.append("text") .style("fill", c1) .style("text-anchor", "middle") .style("font-family", "Helvetica, Arial, sans-serif") .style("font-weight", "bold" ) .style("opacity", 0) .style('font-size', "0.9em") .attr("dy", "2em") .attr("transform", d => `rotate(${90 + d.angle * 360 / (2 * Math.PI)})`) .text(d => d.number); cell2.append("circle") .style("fill", c5) .attr("r", 5); return svg.node(); }32:T6b5, run = async (delay1, delay2, controller) => { // const generator = sieveErathos(N); // const handleNewState = (state) => { if(state === undefined) return; const newPrime = state[1] !== 0 && state[2].length === 0; const newPrimeMultiple = state[2].length > 0; const firstPrime = state[0] === 0; // p = 2 const lastPrime = state[1] === 0; // end // update running data if (newPrime){ if (!firstPrime) runningData.slice(-1)[0].current = false; runningData.push({ prime: state[1], multiples: [], current: true }); } else if (lastPrime) runningData.slice(-1)[0].current = false; else if (newPrimeMultiple) runningData.slice(-1)[0].multiples.push(state[2].slice(-1)); // update visualization update(); }; // start generator iteration let next; do { // check pause if (controller && controller.pause) while(controller.pause){ await Promises.delay(30); }; // iterate next = generator.next(); if (next.value){ handleNewState(next.value); // wait let delay = next.value[2].length > 0 ? delay2 : delay1; if (delay > 0) await Promises.delay(delay); // check stop if (controller && controller.stop){ generator.return(); } } } while (!next.done); // end(); }33:T5e3,update = () => { const svg = d3.select("svg.graph"); const current = runningData.slice(-1)[0]; const previous = runningData.length > 1 ? runningData.slice(-2)[0] : undefined; svg.select("#_" + current.prime) .select("rect") .style("fill", current.current ? c3 : c2); svg.select("#c_" + current.prime) .select("circle") .style("fill", current.current ? c3 : c2); svg.select("#c_" + current.prime) .select("text") .style("opacity", 1); if (previous) { svg.select("#_" + previous.prime) .select("rect") .style("fill", c2); svg.select("#c_" + previous.prime) .select("circle") .style("fill", c2); } if (current.multiples.length > 0) { const n = current.multiples.slice(-1)[0]; const s = svg.select("#_" + n); const s2 = svg.select("#c_" + n); svg.select("#status").text(`step 3: multiples of ${current.prime}`); s.select("rect") .classed("marked", true) .attr("opacity", 0.8) .style("fill", c4); s2.select("circle") .classed("marked", true) .attr("opacity", 0.8) .style("fill", c4); s.select("text") .style("font-weight", "normal"); } else { svg.selectAll(".marked") .attr("opacity", 0.4) .style("fill", c5); d3.select("svg.graph").select("#status").text(`step 4-5`); } }; 34:[] 2e:{"title":"Sieve of Eratosthenes","cells":[{"id":0,"value":"md`# Sieve of Eratosthenes`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"md `In mathematics, the **[Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)** is a simple, ancient algorithm for finding all prime numbers up to any given limit (**N**). It has been attributed to [Eratosthenes of Cyrene](https://en.wikipedia.org/wiki/Eratosthenes), 276 BC - 194 BC, greek mathematician. \n\n> *Reminder: a prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.*\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":715,"value":"md `### Animation\nThe goal of this notebook is to provide a visual illustration of how this simple algorithm works and not about the implementation itself. See below (**Eratosthenes' method**) for more details about this algorithm. Note that the implementation is the basic one, without any optimization or refinement.\nClick on *restart* button to re-launch the algorithm.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":708,"value":"md `### Eratosthenes' method:\n1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., N).\n1. Initially, let p equal 2, the smallest prime number.\n1. Enumerate the multiples of p by counting in increments of p from 2p to N, and mark them in the list (these will be 2p, 3p, 4p, ...).\n1. Find the first number greater than p in the list that is not marked. If there was no such number, stop. \n1. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.\n1. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below N.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"md `### Algorithm implementation\n**Sieve of Eratosthenes** algorithm implemented as a [Generator Function](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*). The \"**yield**\" values corresponds to the current state of the algorithm process and they are represented as an array of 3 elements:\n\\`\\`\\`\n[p0, p, []] // new prime \"p\" (step 5), previous prime \"p0\"\n[p0, p, [2*p]] // 1st multiple (step 3)\n[p0, p, [2*p, 3*p]] // 2nd multiple (step 3)\n[p0, p, [2*p, 3*p, 4*p]] // ...\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":328,"value":"function* sieveErathos(n) {\n let ints = integers(n);\n let marked = Array(n -1).fill(false);\n let p = 2;\n let p0 = 0;\n let y = [p0, p, []]; // yielded value [prime, [prime multiples]]\n do {\n let i = 2;\n yield y;\n while (p*i <= n){\n y[2].push(p * i)\n yield y;\n marked[p * i - 2] = true;\n i++;\n }\n ints = ints.filter(d => d > p && !marked[d -2]);\n p0 = p;\n p = ints[0];\n y = [p0, p, []];\n } while( ints.length > 0 && p <= n);\n return [p0, 0, []]; // end generator\n };","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"md `## Animation\nThe run function iterate though the Generator **sieveErathos()**. It is responsible for controling the algorithm (pause/continue, stop, ...) and add delays for visualisation purpose. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":336,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":301,"value":"end = () => {\n d3.select(\"#start\").attr(\"disabled\", null);\n d3.select(\"#reset\").attr(\"disabled\", null);\n d3.select(\"#stop\").attr(\"disabled\", true);\n d3.select(\"#pause\").attr(\"disabled\", true);\n d3.select(\"svg.graph\").select(\"#status\").text(\"step 6\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":142,"value":"reset = () => {\n let svg = d3.select(\"svg.graph\");\n let cell = svg.selectAll(\"g.cell\");\n let cell2 = svg.selectAll(\"g.cell2\");\n cell.select(\"rect\")\n .classed(\"marked\", false)\n .style(\"opacity\", 1)\n .style(\"fill\", c5);\n cell2.select(\"circle\")\n .classed(\"marked\", false)\n .style(\"opacity\", 1)\n .style(\"fill\", c5);\n cell2.select(\"text\")\n .style(\"opacity\", 0);\n cell.select(\"text\")\n .style(\"font-weight\", \"bold\");\n runningData.length = 0;\n svg.select(\"#status\").text(\"step 1\");\n svg.selectAll(\"path\").remove();\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":593,"value":"md `## Colors`","pinned":false,"hidden":false,"mode":"ojs"},{"id":661,"value":"viewof c2 = color({\n value: d3.schemeCategory10[8],\n title: \"Prime Numbers\",\n})//\"#c2e699\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":937,"value":"viewof c3 = color({\n value: d3.schemeCategory10[3],\n title: \"Current Prime\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":945,"value":"viewof c4 = color({\n value: d3.schemeCategory10[1],\n title: \"Current Prime Multiples\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":947,"value":"viewof c5 = color({\n value: \"#bbbbbb\",\n title: \"Multiple of Prime (marked)\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":591,"value":"c1 = \"#1F4057\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":414,"value":"md `## Graph`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"N= 100;","pinned":false,"hidden":false,"mode":"ojs"},{"id":198,"value":"cellSize = (imgWidth ) / Math.sqrt(N) - padding ","pinned":false,"hidden":false,"mode":"ojs"},{"id":1125,"value":"imgWidth = 0.4 * width","pinned":false,"hidden":false,"mode":"ojs"},{"id":613,"value":"padding = 3","pinned":false,"hidden":false,"mode":"ojs"},{"id":616,"value":"H = (d3.max(gridata, d => d.row) + 1) * (cellSize + padding) + 20;","pinned":false,"hidden":false,"mode":"ojs"},{"id":1073,"value":"function getPoints(selection){\n const regex = /translate\\(\\s*(-?[\\d.]*)\\s*[,]\\s*(-?[\\d.]*)\\s*/;\n const points = [];\n selection.forEach(d => {\n let m = d.attr(\"transform\").match(regex);\n points.push([m[1], m[2]]);\n });\n \n return points;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"md `## Data`","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"gridata = {\n let pas = Math.ceil(Math.sqrt(N)) ;\n let data = [];\n let row = 0;\n let a0 = 2 * Math.PI / N;\n integers(N).forEach((d, i) => {\n let n = {\n number: d,\n isPrime: d === 2 ? true : false,\n marked: false,\n angle: i * a0 -Math.PI / 2\n };\n data.push(n);\n n.col = (d - 2) % pas + 1;\n if (n.col === 1)\n row++;\n n.row = row;\n });\n return data.sort((a, b) => b.number < a.number);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":528,"value":"runningData = []","pinned":false,"hidden":false,"mode":"ojs"},{"id":431,"value":"legendData = [\n {\n val: \"n\",\n color: c5,\n label: \"initial state\",\n opacity: 1\n },\n {\n val: \"p\",\n color: c3,\n label: \"current prime\",\n opacity: 1\n },\n \n {\n val: \"p.i\",\n color: c4,\n label: \"multiples of current prime\",\n opacity: 1\n },\n {\n val: \"p\",\n color: c2,\n label: \"prime number\",\n opacity: 1\n },\n {\n val: \"n\",\n color: c5,\n label: \"multiples of primes\",\n opacity: 0.4\n },\n ];","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"md `*generate an array of integers from 2 to n:*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"integers = n => [...Array(n + 1).keys()].splice(2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":410,"value":"md `## Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"id":910,"value":"import {slider,color} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}