1
\$\begingroup\$

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);
\$\endgroup\$
  • 1
    \$\begingroup\$ You didn't properly declared your variables in the function, so they end up in the global namespace too. \$\endgroup\$ – zord Dec 22 '14 at 23:27
  • \$\begingroup\$ 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 \$\endgroup\$ – gengkev Jan 2 '15 at 16:58
  • \$\begingroup\$ Oh, here: stackoverflow.com/questions/500504/… \$\endgroup\$ – gengkev Jan 2 '15 at 17:01
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.