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

my task produce array containing prime numbers 12-digit number.

i tried emulate sieve of eratosthenes first making function enumerate produces array containing every integer 2 num:

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

then made function leaveonlyprimes loops through , removes multiples of every array member 1/2 max array (this not end being every integer because array become smaller every iteration):

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

this works fine numbers 50000, higher , browser seems freeze up.

is there version of approach made accommodate larger numbers, or barking wrong tree?

as @willness suggests, should not make single monolithic sieve of size. instead, use segmented sieve of eratosthenes perform sieving in successive segments. @ first segment, smallest multiple of each sieving prime within segment calculated, multiples of sieving primes marked composite in normal way; when sieving primes have been used, remaining unmarked number in segment prime. then, next segment, smallest multiple of each sieving prime multiple ended sieving in prior segment, , sieving continues until finished.

consider example of sieving 100 200 in segments of 20; 5 sieving primes 3, 5, 7, 11 , 13. in first segment 100 120, bitarray has 10 slots, slot 0 corresponding 101, slot k corresponding 100 + 2*k* + 1, , slot 9 corresponding 119. smallest multiple of 3 in segment 105, corresponding slot 2; slots 2+3=5 , 5+3=8 multiples of 3. smallest multiple of 5 105 @ slot 2, , slot 2+5=7 multiple of 5. smallest multiple of 7 105 @ slot 2, , slot 2+7=9 multiple of 7. , on.

function primes takes arguments lo, hi , delta; lo , hi must even, lo < hi, , lo must greater square root of hi. segment size twice delta. array ps of length m contains sieving primes less square root of hi, 2 removed since numbers ignored, calculated normal sieve of eratosthenes. array qs contains offset sieve bitarray of smallest multiple in current segment of corresponding sieving prime. after each segment, lo advances twice delta, number corresponding index i of sieve bitarray 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)   0 m-1     qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]   while lo < hi     0 delta-1       sieve[i] := true     0 m-1       j qs[i] delta step ps[i]         sieve[j] := false       qs[i] := (qs[i] - delta) % ps[i]     0 delta-1       t := lo + 2*i + 1       if sieve[i] , t < hi         output t     lo := lo + 2*delta 

for sample given above, called primes(100, 200, 10). in example given above, qs [2,2,2,10,8], corresponding smallest multiples 105, 105, 105, 121 , 117, , reset second segment [1,2,6,0,11], corresponding smallest multiples 123, 125, 133, 121 , 143.

the value of delta critical; should make delta large possible long @ fits in cache memory, speed. use language's library bitarray, take single bit each sieve location. if need simple sieve of eratosthenes calculate sieving primes, favorite:

function primes(n)   sieve := makearray(2..n, true)   p 2 n step 1     if sieve(p)       output p       p * p n step p           sieve[i] := false 

i'll leave translate javascript. can see more algorithms involving prime numbers @ my blog.