Coding › Prime Number Generator

This tutorial will provide you with a very basic introduction to programming in assembly language.

Table of Contents

Source Code

Introduction

I attempted to teach myself assembly language a few years ago, which some may think proves my insanity; but it's actually quite fun. I used the tutorial that Dr. Paul Carter has helpfully put online at http://www.drpaulcarter.com/pcasm/index.php.

There are many reasons to learn assembly language, but the main reason is so that when you're writing high-level code in C++, C#, VB etc., you know what is going on "under the hood", as it were, which means that you can (or rather should) be able to write more efficient code...

The following was my first, and very small, project in assembly. I have put it online with a few explanatory notes in the hope that anybody else starting to learn assembly would find it useful.

The purpose of this program is to generate a list of all the prime numbers up to a certain limit, specified by the user. It will use the Sieve of Eratosthenes, which is an algorithm invented by an ancient Greek scholar. (I'm not going to go into details about how this algorithm works - if you're interested, have a look here).

We're not going to write the whole program in assembly - the code required to do input from, and output to, the screen, is fairly lengthy. All we will use assembly for is just the part of the program that actually performs the calculation. This is a reflection of how assembly would be used in real-world programming.

Program Shell

So first we need to set up the shell for our program. The following code just prompts for user input, runs the actual calculation function which we will define later, and then outputs either to the screen or a file.

class Test()
{
  System.println("Hello World");
}

The Nitty-Gritty

Our program relies on just one assembly language function to do all of the calculation. There isn't even very much to the function - it's just a couple of nested for loops.

The basic idea of the Sieve of Eratosthenes is that if, for instance, 2 is a prime number, then all the multiples of 2 can't, by definition, be primes since they are divisible by 2, so they are "crossed off" from the list. The "sieve" then moves on to the next number, checks to see if it has already been "crossed off", and if it hasn't we know that is a prime; so once again, all the multiples of this number are crossed off as they cannot be primes either.

This method corresponds in programming terms to two for loops. The first, or outer, loop increments a counter by one until we reach half of the limit set by the user. It is only necessary to count to half this number, because we know by that point that all multiples have been "checked".

for (i = 2; i <= (limit / 2); i++)

The inner for loop increments a second counter.

  for (j = 2; j <= (limit / i); j++)

The calculation.

    p[i * j - 1] = 1;

Modify j loop and array index to eliminate div by i.

for (i = 2; i <= (limit / 2); i++)
  for (j = (2 * i); j <= limit; j += i)
    p[j-1]=1;