Skip to content

Instantly share code, notes, and snippets.

@maxArturo

maxArturo/Readme.md

Last active August 29, 2015 14:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save maxArturo/1e3abba3ddcc66017e99 to your computer and use it in GitHub Desktop.
Save maxArturo/1e3abba3ddcc66017e99 to your computer and use it in GitHub Desktop.
Download ZIP
Sieve of Erathosthenes
Raw
Readme.md

##Visualized Sieve of Erathosthenes## After starting to refresh myself up on algorithms, I rediscovered this old favorite. It is an old, old algorithm to find prime numbers. Alas - I struggled for a bit on the assumptions (such as starting on n^2 for each sequential sieve iteration). Once I fully understood it, I was left with a want to visualize the iterations. As such, I've made this visualization to hopefully help anyone just first encountering the algorithm.

  • The current number used for sieving is indicated with a pipeline
  • Numbers which are sieved are highlighted in the color of their factor
  • Numbers which have been used to sieve are underlined, and
  • A circle jumps around to indicate the square of the current sieving number.

It is not optimized, so as to demonstrate the need to jump over previously-sieved numbers, as well as to show the effects of starting at n^2 with a highlighted circle.

An interesting and didactic effect of seeing a long list of numbers (160 in this case) is that one can see how only the primary numbers sieve any numbers down the list; the composite numbers will leave the list unaffected.

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
text {
font: bold 30px monospace;
}
.prime {
fill: #DF0174;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
/*global d3 */
var maxNumber = 160;
var width = 800,
height = maxNumber * 3,
currNumber = 0,
colorScale = d3.scale.category20();
var sieveArray = draw_sieve(maxNumber);
var svg = d3.select("body")
.append("svg")
.attr("height", height)
.attr("width", width)
.append("g");
//highlighter circle points us to the square of the number being
//sieved.
var highlighter = svg.append("circle")
.attr("cx", 10)
.attr("cy", 10)
.attr("r", 15)
.attr("fill", "steelblue");
var intervalID = setInterval(function() {
currNumber += 1;
if (Math.pow(currNumber, 2) >= maxNumber) {
clearInterval(intervalID);
return;
}
update(sieveArray);
}, 1500);
function update(data) {
var currColor = colorScale(Math.random()); //add variability in colors
var numbers = svg.selectAll("text")
.data(data);
//update with color hints. Underlined numbers have been sieved for their
//multiples, and numbers with a '|' are current.
numbers
.transition()
.duration(750)
.attr("fill", function(d) {
if (((d % currNumber === 0) && (d > currNumber) &&
!(d3.select(this).attr("fill"))) || (d == currNumber)) {
d3.select(this).attr("class", "");
return currColor;
} else {
return d3.select(this).attr("fill");
}
})
.style("text-decoration", function(d) {
var currDecoration = d3.select(this).style("text-decoration");
return d == currNumber && (currDecoration == "none") ? "underline" : currDecoration;
})
.text(function(d) {
return d == currNumber ? currNumber + "|" : d;
});
//add new elements
numbers.enter()
.append("text")
.attr("y", yTextOffset)
.attr("x", xTextOffset)
.attr("dy", ".3em")
.attr("dx", "-.1em")
.attr("class", "prime")
.text(function(d) {
return d;
});
highlighter
.transition()
.duration(750)
.attr("cx", xTextOffset(Math.pow(currNumber, 2)) + 15)
.attr("cy", yTextOffset(Math.pow(currNumber, 2)));
}
function yTextOffset(d) {
var shift = (d % 10) ? 0 : -30;
return 20 + (30 * Math.floor(d / 10)) + shift;
}
function xTextOffset(d) {
return (d % 10) ? (d % 10) * 70 : 10 * 70;
}
function draw_sieve(n) {
var allNumbers = [];
for (var i = n; i >= 1; i--) {
allNumbers[i] = i;
}
return allNumbers;
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment