Creating the Sieve of Eratosthenes Animation in Vue

✔︎ Last updated on March 29th, 2024

In this article, you will learn how to create an animation to simulate the Sieve of Eratosthenes algorithm in Vue.js. This animation is inspired by the GIF on this article’s Wikipedia page.

I love coding. I don’t do it professionally as I made some short-sighted choices in my career but the love for coding refuses to die down in me.

As a result, most of my free time goes towards learning coding and then building some stuff with the things I learn. One of the things that I picked up after learning JavaScript was the Vue.js framework and it opened a whole new world of opportunities before me.

The thing that struck me most about Vue was how much I was able to create with so few lines of code.

Recently, when I was deep down in a rabbit hole about something unrelated, I happened upon a Wikipedia article on the Sieve of Eratosthenes where I saw this animation:

This is a nice little concept — demo the algorithm progressing through an animation.

Soon, a thought crossed my mind — maybe I can build that in Vue.

Soon, I fired up my code editor, initialized a new project through the Vue command line, and began writing code. After hours of coding (and bleary-eyes), this is what my animation looks like:

Let’s learn how you can create this animation yourself.

What is the Sieve of Eratosthenes

The Sieve of Eratosthenes is a clever way to find all the prime numbers up to a given limit. It works by starting with a list of all the numbers from 2 to the limit you want to check.

You start by marking the number 2 as prime, then, you strike out all its multiples, since they can’t be prime. Then you move on to the next unstruck number (3) and mark it prime. Then you strike out all its multiples. You repeat this process numerous times and any number that is left unstruck is prime.

This algorithm is efficient because once you find a prime, you know that all its multiples are not prime. So, you don’t need to check them individually.

Also read: How to Lighten or Darken a Color with Pure CSS

Also, finding primes through the Sieve of Eratosthenes is less CPU intensive than other algorithms because in this algorithm, we rule out composites using multiplication whereas in some other algorithms, we have to use division to rule out composites.

(Multiplication is much faster for computers to perform than division. That’s why you should multiply by 0.5 rather than dividing by 2).

Sieve of Eratosthenes Algorithm

First, I will explain the algorithm and its optimization and then we will discuss how you can add colors to

This algorithm works in passes. We start with two empty arrays — one for primes and another for composites. At each pass, we put the uncrossed out number in the primes array and all its multiples in the composite array.

Suppose, we are to find prime numbers from 1 to 200, this is what these arrays should look like on each pass:

Here’s a little optimization trick: — after finding a prime number, you don’t have to start multiplying it from 2 to find its multiples. For example, for the prime number 11, you could skip its multiples from 2 to 10 and start straight from its square i.e. 11 x 11 to find its composites.

Why?

As you can see, in the above table, the new (unexplored) composites for a corresponding prime number start with its square — 4 for 2, 9 for 3, 25 for 5, 49 for 7, 121 for 11, and so on.

That’s because all the multiples of a prime with smaller numbers than itself have already been struck out by the smaller primes in earlier passes. For example, you won’t find 6 in the composites array of 3 (a prime) because 6 was already crossed out by 2 in the earlier pass. Similarly, for the prime 5, composites like 10, 15 & 20 have already been struck out by smaller primes 2 and 3.

Therefore the only way we are going to find out new composite numbers is by starting at the square of the corresponding prime number.

Also read: How to Make a Radar Scanner Animation in CSS (Using pseudo-elements)

Keeping this optimization in mind, here’ is the full code for finding out the prime numbers using the Sieve of Eratosthenes method:

generatePrimes (limit) {
	let composites = [];
	let primes = [];
	let i = 2;
	while (i <= limit) {
		if (!composites.includes(i)) {
			// Its a prime
			primes.push(i);
			
			// code to apply a color to this prime's block will come here 👇
			
		
			for (let j = i * i; j <= limit; j = j + i) {
			  // mark its multiples as composite
				if (composites.includes(j)) {
				  // if already marked composite, skip it
					continue;
				}
				composites.push(j);
				// code to apply a color to this composite's block will come here 👇

			}
		}
		// check for the next number
		i = i + 1;
	}
	console.log(primes);
}

I have highlighted the lines in the above code where the code to color the individual blocks will go. I have skipped it for now, but we will soon see its implementation.

Animating the algorithm

Up to this point, you can’t see any animation. Even if I set the colors to all the primes and composites using the document.getElementById("#id").style.backgroundColor, the colors would be set but you wouldn’t see the animation. That’s because the computations are so fast that all the numbers are colored instantly.

To see or perceive the animation, we have to introduce a wait time between the statements of the algorithm.

Since there’s no built-in wait() function in JavaScript, we have to hack together a solution so that the colors to these numbers are applied after some delay.

After much trial and error, I built this function which takes three arguments: the id of element, a color, and a global increasing counter variable to set an appropriate delay between the function calls. This is what it looks like:

var counter = 1; // global variable to time function calls

delayed(id, color, type) {
	setTimeout(() => {
    document.getElementById(id).style.backgroundColor = color;
	}, 100 * this.counter);
	
	counter = counter+1; // increase the counter
},

I have set the delay for the setTimeout functions in multiples of 100ms. You can adjust the speed of animation by ramping it up or dialing it down.

Considering the discussion so far, I adapted this code for a Vue program. You can see it here in this Codepen in all its glory:

<template>
	<div id="#app">
		<h1>Seive of Eratosthenes</h1>
		<div class="setup">
			<div class="block" v-for="n in numbers" :key="n" :ref="n">{{ n }}</div>
		</div>
		<hr />
		<div>
			<h2>Primes:</h2>
			<span v-for="n in primes">{{ n }},</span>
		</div>
	</div>
</template>

<script>
export default {
	data() {
		return {
			limit: 100,
			numbers: Array.from({ length: 100 }, (_, index) => index + 1),
			timeGap: 150,
			counter: 0,
			primes: []
		};
	},
	created() {
		console.clear();
	},
	mounted() {
		this.makePrimes();
	},
	methods: {
		makePrimes() {
			let composites = [];
			let primes = [];
			let i = 2;
			while (i <= this.limit) {
				if (!composites.includes(i)) {
					// Its a prime
					primes.push(i);
					this.delayed(i, `hsl(${(i * 10) % 360}, 80%, 50%, .7)`, "prime");

					// mark its multiples as composite
					for (let j = i * i; j <= this.limit; j = j + i) {
						if (composites.includes(j)) {
							// if already marked composite, don't change its color
							continue;
						}
						composites.push(j);
						this.delayed(j, `hsl(${(i * 10) % 360}, 80%, 50%, .3)`, "composite");
					}
				}
				// check for the next prime
				i = i + 1;
			}
		},
		delayed(el, color, type) {
			this.counter += 1;
			setTimeout(() => {
				this.$refs[el][0].style.backgroundColor = color;
				if (type === "prime") this.primes.push(el);
			}, this.timeGap * this.counter);
		}
	}
};
</script>

<style>
body {
	font-family: Avenir, system-ui;
	padding: 30px;
	max-width: 600px;
	margin: auto;
	display: grid;
	place-content: center;
	text-align: center;
}

#app {
	font-family: avenir, system-ui;
	-webkit-font-smoothing: antialiased;
	-moz-osx-font-smoothing: grayscale;
	text-align: center;
	color: #2c3e50;
	margin-top: 60px;
	text-transform: uppercase;
}

.block {
	display: inline-grid;
	place-content: center;
	width: 40px;
	text-align: center;
	aspect-ratio: 1;
	border-radius: 4px;
	border: 1px solid #ddd;
	margin: 2px;
}

h1,
h2,
h3 {
	font-size: 1.3rem;
	margin: 20px;
}
</style>

Why not bind classes dynamically

One thing may have popped into your mind: why not use dynamic classes and add or remove them based on the boolean value of a variable?

That’s because a single variable (say isVisited) is not sufficient to keep track of the state of each of these numbers. I will either have to maintain an array of such variables separately or convert my numbers array into an array of objects each containing two properties:

const numbersArray = [
  {
    value: 2,
    isVisited: false,
  },
  {
    value: 3,
    isVisited: false,
  },
  .
  .
  // and so on
];

This is needlessly complicated for what I want to achieve. Another option is to convert each of these numbers into a separate component. This would eliminate the need for maintaining an array of isVisited variables. But, for such a simple program, adding components is making things unnecessarily complicated.

Also read: How to Create a Chessboard Pattern in CSS

Overall, I’m pretty satisfied with what Vue has allowed me to do with so little code. But I’m sure there are a million ways to improve upon this code. I’m just a beginner. I’d appreciate if you could suggest some improvements in this code.

You can comment down below or find me on Twitter here.

Thanks for reading.