# Prime Number Sieve Optimization

I've written my own prime number sieve in JavaScript. It loops through numbers 1-100 and puts them in one of two arrays, depending on if it is composite or prime.

I was wondering if there are any inefficient or unnecessary parts of my code that might be slowing down the program. Is there anything I can do so it will work for larger numbers too?

//  Creating variables to use later
var cORp;
var compNums = [];

// Create numberSieve function
function numberSieve(x) {

// 0 and 1 are not prime or composite
if (x < 2 && x >= 0) {
cORp = 'neither';
}

// All negative numbers are composite
else if (x < 0) {
cORp = 'composite';
}

// Sieve for positive numbers above 1
else {

// Some more variables for later use
possibleFactors = [];
zFactors = [];
matchingFactors = [];

// Takes all numbers that are half of x and below because they are possible factors
for (i=2; i < x/2+1; i++) {
possibleFactors.push(i);
}

// Takes all possible factors and divides x by them
for (i=0; i < possibleFactors.length; i++) {
z = x/possibleFactors[i];
zFactors.push(z);
}

// Checks if the x divided by the possible factors is equal to any of the other possible factors
for (i in possibleFactors) {
if (zFactors.indexOf(possibleFactors[i]) !== -1) {
matchingFactors.push(possibleFactors[i]);
}
}

// Checks if there are any matching factors
if (matchingFactors.length !== 0) {
cORp = 'composite';
}
else {
cORp = 'prime';
}
}

// Prime numbers go to one array, Composite numbers go to another
if (cORp === 'prime') {
}
else if (cORp === 'composite') {
compNums.push(x);
}
}

// For each number 0-100 runs the sieve
a=0;
while (a <= 100) {
numberSieve(a);
a++;
}

// Prints out the prime number and composite number arrays
console.log("Composite Numbers: " + compNums);

• You didn't properly declared your variables in the function, so they end up in the global namespace too. – zord Dec 22 '14 at 23:27
• Also on general code style, I've learned to be quite averse to for...in in javascript, though I can't remember exactly why, other than a lot of complications for non-trivial objects. A regular for loop works just as well – gengkev Jan 2 '15 at 16:58
• Oh, here: stackoverflow.com/questions/500504/… – gengkev Jan 2 '15 at 17:01

Style

The while loop definitly looks like a for loop to me.

Clearer function

Your function numberSieve does not many things. It would be simpler if it was to simply return a value and this value was used afterward to fill arrays.

If we are doing so, we could take this chance to make clear what it returns : it could return whether x is prime or not. By renaming it isPrime, things would be more straightforward.

Also, if you do so, you realise that you can start your loop from 2 if you want to get the same output as you had before.

Here is the corresponding code :

// Create isPrime function
function isPrime(x) {

// 0 and 1 are not prime
if (x < 2) {
return false;
}
// Sieve for positive numbers above 1
else {
// Some more variables for later use
possibleFactors = [];
zFactors = [];
matchingFactors = [];

// Takes all numbers that are half of x and below because they are possible factors
for (i=2; i < x/2+1; i++) {
possibleFactors.push(i);
}

// Takes all possible factors and divides x by them
for (i=0; i < possibleFactors.length; i++) {
z = x/possibleFactors[i];
zFactors.push(z);
}

// Checks if the x divided by the possible factors is equal to any of the other possible factors
for (i in possibleFactors) {
if (zFactors.indexOf(possibleFactors[i]) !== -1) {
matchingFactors.push(possibleFactors[i]);
}
}

// Checks if there are any matching factors
return (matchingFactors.length == 0);
}
}

var compNums = [];

// For each number 0-100 runs the sieve
for (a = 2; a<= 100; a++) {
if (isPrime(a))
else
compNums.push(a);
}

// Prints out the prime number and composite number arrays
print("Composite Numbers: " + compNums);


Clearer algorithm

You don't need to handle arrays to know whether a number divides or not anyther number. You can just use the modulo operator.

function isPrime(x) {

// 0 and 1 are not prime
if (x < 2) {
return false;
}
// Sieve for positive numbers above 1
else {
// Takes all numbers that are half of x and below because they are possible factors
for (i=2; i < x/2+1; i++) {
if (x % i == 0)
return false;
}
return true;
}
}


A smarter algorithm

At the moment, you look for divisors going up to x/2 + 1. Actually, if there are any divisors, there will be a least one divisor d such that $$d \le sqrt(x)$$

Therefore, instead of having a algorithm with completity O(N), we have O(sqrt(N)) which is much faster for big values of N.

   // Takes all numbers that are half of x and below because they are possible factors
for (i=2; i <= Math.sqrt(x); i++) {
if (x % i == 0)
return false;
}
return true;


A more appropriate algorithm

If you want to generate a list of primes (and non-primes) in an efficient way, you should have a look at the Sieve of Eratosthenes.