需要关于如何在 JavaScript 中分解非常大的数字的提示/建议 [英] Need a hint/advice as to how to factor very large numbers in JavaScript

问题描述

我的任务是生成一个数组，其中包含最多 12 位数字的所有质数.

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

我试图模拟 埃拉托色尼筛网，首先创建一个函数 enumerate 生成一个包含从 2 到 num 的每个整数的数组:

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;
};

然后我创建了一个函数 leaveOnlyPrimes，它循环并从数组中删除每个数组成员的倍数，最多为 1/2 max(这不会最终成为每个整数，因为每次迭代数组都会变小):

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);   
    }
};

这适用于高达约 50000 的数字，但任何高于该数字的数字都会导致浏览器冻结.

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?

推荐答案

最多 12 位是 100,000,000,000.这是很多素数(~ N/log N = 3,948,131,653).

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

所以，制作一个高达 10^6 的筛子，将其压缩成约 78,500 个核心素数的数组，并使用它们逐段筛选直至您的目标.使用最多为段当前上限的平方根的素数.通常选择段的大小以使其适合系统缓存.筛选每个片段后，收集其质数.

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.

这篇关于需要关于如何在 JavaScript 中分解非常大的数字的提示/建议的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！