Need a hint/advice as to how to factor very large numbers in JavaScript

Question

My task is to produce an array containing all the prime numbers up to a 12-digit number.

I tried to emulate the Sieve of Eratosthenes by first making a function enumerate that produces an array containing every integer from 2 to num:

var enumerate = function(num) {
    array = [];
    for (var i = 2; i <= num; i++) {
        array.push(i);
    }
    return array;
};

Then I made a function leaveOnlyPrimes which loops through and removes multiples of every array member up to 1/2 max from the array (this does not end up being every integer because the array become smaller with every iteration):

var leaveOnlyPrimes = function(max,array) {
    for (var i = 0; array[i] <= max/2; i++) {
        (function(mult,array) {
            for (var i = mult*2; i <= array[array.length-1]; i += mult) {
                var index = array.indexOf(i);
                if (index !== -1) {
                    array.splice(index,1);
                }
            }
        })(array[i],array);   
    }
};

This works fine with numbers up to about 50000, but any higher than that and the browser seems to freeze up.

Is there some version of this approach which could be made to accommodate larger numbers, or am I barking up the wrong tree?

Did you look at http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms — jeremy, Aug 09 '13 at 19:03
That looks very useful. I'll definitely check it out if I give up trying to figure this out meself. — user2493615, Aug 09 '13 at 19:08
I'm no expert, but my guess would be that the problem has to do with removing lots of items one-at-a-time from a large array. You could test this idea--rather than removing non-primes, you could create a second array and push the primes into it. — SaganRitual, Aug 09 '13 at 20:05

Will Ness · Answer 1 · 2013-12-07T15:19:53.923

up to 12 digits is 100,000,000,000. That's a lot of primes (~ N/log N = 3,948,131,653).

So, make a sieve up to 10^6, compress it into the array of ~78,500 core primes, and use them to sieve segment by segment all the way up to your target. Use primes up to the square root of the current upper limit of the segment. The size of the segment is usually chosen so that it fits into system cache. After sieving each segment, collect its primes.

This is known as segmented sieve of Eratosthenes.

score 1 · Answer 2 · answered Aug 09 '13 at 23:36

As @WillNess suggests, you should not make a single monolithic sieve of that size. Instead, use a segmented Sieve of Eratosthenes to perform the sieving in successive segments. At the first segment, the smallest multiple of each sieving prime that is within the segment is calculated, then multiples of the sieving primes are marked composite in the normal way; when all the sieving primes have been used, the remaining unmarked number in the segment are prime. Then, for the next segment, the smallest multiple of each sieving prime is the multiple that ended the sieving in the prior segment, and so the sieving continues until finished.

Consider the example of sieving from 100 to 200 in segments of 20; the 5 sieving primes are 3, 5, 7, 11 and 13. In the first segment from 100 to 120, the bitarray has 10 slots, with slot 0 corresponding to 101, slot k corresponding to 100 + 2*k* + 1, and slot 9 corresponding to 119. The smallest multiple of 3 in the segment is 105, corresponding to slot 2; slots 2+3=5 and 5+3=8 are also multiples of 3. The smallest multiple of 5 is 105 at slot 2, and slot 2+5=7 is also a multiple of 5. The smallest multiple of 7 is 105 at slot 2, and slot 2+7=9 is also a multiple of 7. And so on.

Function primes takes arguments lo, hi and delta; lo and hi must be even, with lo < hi, and lo must be greater than the square root of hi. The segment size is twice delta. Array ps of length m contains the sieving primes less than the square root of hi, with 2 removed since even numbers are ignored, calculated by the normal Sieve of Eratosthenes. Array qs contains the offset into the sieve bitarray of the smallest multiple in the current segment of the corresponding sieving prime. After each segment, lo advances by twice delta, so the number corresponding to an index i of the sieve bitarray is lo + 2 i + 1.

function primes(lo, hi, delta)
  sieve := makeArray(0..delta-1)
  ps := tail(primes(sqrt(hi)))
  m := length(ps)
  qs := makeArray(0..m-1)
  for i from 0 to m-1
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]
  while lo < hi
    for i from 0 to delta-1
      sieve[i] := True
    for i from 0 to m-1
      for j from qs[i] to delta step ps[i]
        sieve[j] := False
      qs[i] := (qs[i] - delta) % ps[i]
    for i from 0 to delta-1
      t := lo + 2*i + 1
      if sieve[i] and t < hi
        output t
    lo := lo + 2*delta

For the sample given above, this is called as primes(100, 200, 10). In the example given above, qs is initially [2,2,2,10,8], corresponding to smallest multiples 105, 105, 105, 121 and 117, and is reset for the second segment to [1,2,6,0,11], corresponding to smallest multiples 123, 125, 133, 121 and 143.

The value of delta is critical; you should make delta as large as possible so long at it fits in cache memory, for speed. Use your language's library for the bitarray, so that you only take a single bit for each sieve location. If you need a simple Sieve of Eratosthenes to calculate the sieving primes, this is my favorite:

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    if sieve(p)
      output p
      for i from p * p to n step p
          sieve[i] := False

I'll leave it to you to translate to JavaScript. You can see more algorithms involving prime numbers at my blog.

Need a hint/advice as to how to factor very large numbers in JavaScript

2 Answers2

Linked