by

Finding Prime Numbers with JavaScript

Feeling nerdier than usual last night, I was asking myself, and a math teacher (that’s Mrs. Jaye, to you), all sorts of questions about numbers, including prime numbers. Later on, I got to thinking: how would I determine what the prime numbers are in a given range? And then I thought about writing that program. And then I fell asleep — because…narcolepsy at 10:30 is called bed time.

Really? Why?

I have no idea what the practical application of this could possibly be. None. Maybe this is some sort of assignment in some Computer Science or Math class somewhere. Maybe you’d like to learn some basic JavaScript. Maybe you, too, need to earn forgiveness from math teachers everywhere for all those times you fell asleep while they were trying to teach you how to stop counting with your toes.

The Code

I took two years of high school math (which I barely passed), and one highly remedial math course in college (it comprised football players and me). I have the math skills of your typical liberal arts major, so you are within your rights to challenge and/or laugh at my code.

Prime Numbers

A prime number, as a mathematician explained to me last night, is any number that can only be divided by itself, and 1. A prime number shouldn’t be divisible by any more than two numbers. So, our goal is threefold:

  1. count up through a list of numbers, one whole integer at a time
  2. Determine the numbers by which that integer can be divided to make a whole number
  3. Determine if any of those numbers by which my integer can be divided are not 1, or the integer itself

Start a for loop

The first thing I thought was that I’d need two arrays: an array for regular integers and an array for prime numbers. I also set up the for loop to start at zero, rather than my start number. You’ll see why in a minute.

    var numArray = [],
        primeArray = [],
        start =  0,
        end = 20;
    for (var i = 0; i < end; i++) {
    }

Add Numbers to the array

My thinking was that, as I count up, I’ll need to keep track of the available numbers by which I should divide my integer. So I push my integer to my numArray. Also, inside of my for loop, I created a divisArray to keep track of the numbers by which I can divide my integer.

    var numArray = [],
        primeArray = [],
        start = 0,
        end = 20;
    for (var i = 0; i < end; i++) {
        var divisArray = [];
        numArray.push(i);

    }

Discover the divisible numbers

Now that I’m keeping track of the numbers as I count up, I’m going to loop through those, testing to see if my integer is divisible by any of them. I used JavaScript’s modulo( %) operator. You can use % to see if a number, when divided by another, leaves a remainder. If it doesn’t, then I add this number to the array divisArray. If my goal were to simply find the whole numbers that can be multiplied to make by integer, I could stop here.

    var numArray = [],
        primeArray = [],
        start =  0,
        end = 20;
    for (var i = 0; i < end; i++) {
        var divisArray = [];
        numArray.push(i);
        [].forEach.call(numArray, function (num) {
            if (i % num === 0) {
                divisArray.push(num)
            }
        });
    }

Check and see if the number is prime

I cheated here. If I wanted to do this good and proper, I’d actually loop through my divisArray to find either 1 or the integer. I decided to use a much simpler logic: if it’s prime, it must be divisible by only two numbers. Therefore, if there are more than two numbers in my divisArray, it’s not prime.

Inside of my first for loop, I test the length of my divisArray. Not only that, I check to see if the integer is greater than, or equal to, my start variable. I use my start variable here, and not in my first for loop is because starting my for loop anywhere but zero means I never get to test to see if my integer is divisible by earlier numbers. e.g. If I start at 6, then I never get to test 0, 1, 2, 3, 4, 5.

    var numArray = [],
        primeArray = [],
        start =  0,
        end = 20;
    for (var i = 0; i < end; i++) {
        var divisArray = [];
        numArray.push(i);
        [].forEach.call(numArray, function (num) {
            if (i % num === 0) {
                divisArray.push(num)
            }
        });
        if (i >= start && divisArray.length <= 2) {
            primeArray.push(i);
        }
    }

Make the result useful

The aforementioned code will produce an array called primeArray, which should contain my prime numbers. But maybe I want that to be pretty, and useful. In that case, I’ll introduce some HTML, a dab o’CSS, and actually print out the result:

The Big Idea

Math is hard. Thank a math teacher.