1

我正在尝试使用 javascript: 从http://projecteuler.net解决一个数学问题 ：找到所有低于 200 万的素数的总和。当我运行我编写的脚本时，我的浏览器崩溃了（我使用的是 Google Chrome）。这是脚本：

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

document.write("The sum of all the primes below two million is ",total);

该脚本适用于较小的数字（i<100000）。它有什么问题？我该如何解决？谢谢你的帮助。

4

2 回答 2

1

该函数为您检查的每个nisPrime执行n模运算（因为您检查每个小于素数的单个数字作为一个因素）。假设每七个数字中大约有一个是素数，这意味着您在代码段中执行了大约 28,000 次该函数，并且执行了大约 3.92 亿次模运算。很可能，Chrome 正在崩溃，因为它假定 JavaScript 引擎已进入无限循环。isPrime

正如 NullUserException 所说，有更好的方法可以找到素数。

一个简单的改进是只检查小于其平方根的数字的因子。对于a = b * c 的任何数字a，您可以假设b或c小于a的平方根。由于您只需要知道一个因数就可以知道一个数不是素数，因此您只需寻找小于其平方根的因数。正如 lanzz 评论的那样，您也可以跳过偶数。

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

    var s = Math.sqrt(n);

    // iterate by 2 to skip even numbers
    for (var i = 3; i <= s; i += 2)
        if (n % i) return false;

    return true;
}

var total = 3; // 1 + 2

// iterate by 2 to skip even numbers
for (var i = 3; i < 2000000; i += 2)
    if (isPrime(i)) total += i;

不要误会我；这不会改变你算法的O复杂度，而且你仍然会用足够大的数字使 JavaScript 引擎崩溃。但它会提高崩溃的次数。我不确定它是否会达到 200 万。

于 2012-10-24T21:45:30.643 回答
0

试试这个函数，它使用的算法比你的快得多，并且不会因 2M 数字而崩溃：

function isPrime( num ) {
    var testNum = 3;
    var limitNum = num;

    if ( num == 2 )
        return true;

    if ( num % 2 == 0 )
        return false;

    while ( limitNum > testNum ) {
        if ( num % testNum == 0 ) {
            return false;
        }

        limitNum = parseInt( num / testNum );
        testNum += 2;
    }

    return true;
}

我在这里找到它是 VB 代码，我只是将它翻译成 Javascript。

于 2012-10-24T22:11:53.057 回答