Prime Number Sieve Optimization

Question

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 primeNums = [];
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') {
        primeNums.push(x);
    }
    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("Prime Numbers: " + primeNums);
console.log("Composite Numbers: " + compNums);

Answer 1

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 primeNums = [];
var compNums = [];

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

// Prints out the prime number and composite number arrays
print("Prime Numbers: " + primeNums);
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.