How to find prime numbers between 0 - 100?

Here's an example of a sieve implementation in JavaScript:

function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}

Then getPrimes(100) will return an array of all primes between 2 and 100 (inclusive). Of course, due to memory constraints, you can't use this with large arguments.

A Java implementation would look very similar.

Here's how I solved it. Rewrote it from Java to JavaScript, so excuse me if there's a syntax error.

function isPrime (n)
{
    if (n < 2) return false;

    /**
     * An integer is prime if it is not divisible by any prime less than or equal to its square root
     **/

    var q = Math.floor(Math.sqrt(n));

    for (var i = 2; i <= q; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

A number, n, is a prime if it isn't divisible by any other number other than by 1 and itself. Also, it's sufficient to check the numbers [2, sqrt(n)].

Here is the live demo of this script: http://jsfiddle.net/K2QJp/

First, make a function that will test if a single number is prime or not. If you want to extend the Number object you may, but I decided to just keep the code as simple as possible.

function isPrime(num) {
    if(num < 2) return false;
    for (var i = 2; i < num; i++) {
        if(num%i==0)
            return false;
    }
    return true;
}

This script goes through every number between 2 and 1 less than the number and tests if there is any number in which there is no remainder if you divide the number by the increment. If there is any without a remainder, it is not prime. If the number is less than 2, it is not prime. Otherwise, it is prime.

Then make a for loop to loop through the numbers 0 to 100 and test each number with that function. If it is prime, output the number to the log.

for(var i = 0; i < 100; i++){
    if(isPrime(i)) console.log(i);
}

Whatever the language, one of the best and most accessible ways of finding primes within a range is using a sieve.

Not going to give you code, but this is a good starting point.

For a small range, such as yours, the most efficient would be pre-computing the numbers.

I have slightly modified the Sieve of Sundaram algorithm to cut the unnecessary iterations and it seems to be very fast.

This algorithm is actually two times faster than the most accepted @Ted Hopp's solution under this topic. Solving the 78498 primes between 0 - 1M takes like 20~25 msec in Chrome 55 and < 90 msec in FF 50.1. Also @vitaly-t's get next prime algorithm looks interesting but also results much slower.

This is the core algorithm. One could apply segmentation and threading to get superb results.

"use strict";
function primeSieve(n){
  var a = Array(n = n/2),
      t = (Math.sqrt(4+8*n)-2)/4,
      u = 0,
      r = [];
  for(var i = 1; i <= t; i++){
    u = (n-i)/(1+2*i);
    for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true;
  }
  for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1);
  return r;
}

var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);

The loop limits explained:

Just like the Sieve of Erasthotenes, the Sieve of Sundaram algorithm also crosses out some selected integers from the list. To select which integers to cross out the rule is i + j + 2ij ≤ n where i and j are two indices and n is the number of the total elements. Once we cross out every i + j + 2ij, the remaining numbers are doubled and oddified (2n+1) to reveal a list of prime numbers. The final stage is in fact the auto discounting of the even numbers. It's proof is beautifully explained here.

Sieve of Sundaram is only fast if the loop indices start and end limits are correctly selected such that there shall be no (or minimal) redundant (multiple) elimination of the non-primes. As we need i and j values to calculate the numbers to cross out, i + j + 2ij up to n let's see how we can approach.

i) So we have to find the the max value i and j can take when they are equal. Which is 2i + 2i^2 = n. We can easily solve the positive value for i by using the quadratic formula and that is the line with t = (Math.sqrt(4+8*n)-2)/4,

j) The inner loop index j should start from i and run up to the point it can go with the current i value. No more than that. Since we know that i + j + 2ij = n, this can easily be calculated as u = (n-i)/(1+2*i);

While this will not completely remove the redundant crossings it will "greatly" eliminate the redundancy. For instance for n = 50 (to check for primes up to 100) instead of doing 50 x 50 = 2500, we will do only 30 iterations in total. So clearly, this algorithm shouldn't be considered as an O(n^2) time complexity one.

i  j  v
1  1  4
1  2  7
1  3 10
1  4 13
1  5 16
1  6 19
1  7 22  <<
1  8 25
1  9 28
1 10 31  <<
1 11 34
1 12 37  <<
1 13 40  <<
1 14 43
1 15 46
1 16 49  <<
2  2 12
2  3 17
2  4 22  << dupe #1
2  5 27
2  6 32
2  7 37  << dupe #2
2  8 42
2  9 47
3  3 24
3  4 31  << dupe #3
3  5 38
3  6 45
4  4 40  << dupe #4
4  5 49  << dupe #5

among which there are only 5 duplicates. 22, 31, 37, 40, 49. The redundancy is around 20% for n = 100 however it increases to ~300% for n = 10M. Which means a further optimization of SoS bears the potentital to obtain the results even faster as n grows. So one idea might be segmentation and to keep n small all the time.

So OK.. I have decided to take this quest a little further.

After some careful examination of the repeated crossings I have come to the awareness of the fact that, by the exception of i === 1 case, if either one or both of the i or j index value is among 4,7,10,13,16,19... series, a duplicate crossing is generated. Then allowing the inner loop to turn only when i%3-1 !== 0, a further cut down like 35-40% from the total number of the loops is achieved. So for instance for 1M integers the nested loop's total turn count dropped to like 1M from 1.4M. Wow..! We are talking almost O(n) here.

I have just made a test. In JS, just an empty loop counting up to 1B takes like 4000ms. In the below modified algorithm, finding the primes up to 100M takes the same amount of time.

I have also implemented the segmentation part of this algorithm to push to the workers. So that we will be able to use multiple threads too. But that code will follow a little later.

So let me introduce you the modified Sieve of Sundaram probably at it's best when not segmented. It shall compute the primes between 0-1M in about 15-20ms with Chrome V8 and Edge ChakraCore.

"use strict";
function primeSieve(n){
  var a = Array(n = n/2),
      t = (Math.sqrt(4+8*n)-2)/4,
      u = 0,
      r = [];
  for(var i = 1; i < (n-1)/3; i++) a[1+3*i] = true;
  for(var i = 2; i <= t; i++){
    u = (n-i)/(1+2*i);
    if (i%3-1) for(var j = i; j < u; j++) a[i + j + 2*i*j] = true;
  }
  for(var i = 0; i< n; i++) !a[i] && r.push(i*2+1);
  return r;
}

var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);

Well... finally I guess i have implemented a sieve (which is originated from the ingenious Sieve of Sundaram) such that it's the fastest JavaScript sieve that i could have found over the internet, including the "Odds only Sieve of Eratosthenes" or the "Sieve of Atkins". Also this is ready for the web workers, multi-threading.

Think it this way. In this humble AMD PC for a single thread, it takes 3,300 ms for JS just to count up to 10^9 and the following optimized segmented SoS will get me the 50847534 primes up to 10^9 only in 14,000 ms. Which means 4.25 times the operation of just counting. I think it's impressive.

You can test it for yourself;

console.time("tare");
for (var i = 0; i < 1000000000; i++);
console.timeEnd("tare");

And here i introduce you to the segmented Seieve of Sundaram at it's best.

"use strict";
function findPrimes(n){
  
  function primeSieve(g,o,r){
    var t = (Math.sqrt(4+8*(g+o))-2)/4,
        e = 0,
        s = 0;
    
    ar.fill(true);
    if (o) {
      for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
      for(var i = 2; i < t; i++){
        s = Math.ceil((o-i)/(1+2*i));
        e = (g+o-i)/(1+2*i);
        if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
      }
    } else {
        for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
        for(var i = 2; i < t; i++){
          e = (g-i)/(1+2*i);
          if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
        }
      }
    for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
    return r;
  }
  
  var cs = n <= 1e6 ? 7500
                    : n <= 1e7 ? 60000
                               : 100000, // chunk size
      cc = ~~(n/cs),                     // chunk count
      xs = n % cs,                       // excess after last chunk
      ar = Array(cs/2),                  // array used as map
  result = [];
  
  for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
  result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
  result[0] *=2;
  return result;
}


var primes = [];
console.time("primes");
primes = findPrimes(1000000000);
console.timeEnd("primes");
console.log(primes.length);

I am not sure if it gets any better than this. I would love to hear your opinions.