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:
- count up through a list of numbers, one whole integer at a time
- Determine the numbers by which that integer can be divided to make a whole number
- 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.