이 스크립트를 실행하면 브라우저에서 javascript가 작동하지 않습니다. 무엇이 문제입니까?

Question

저는 http://projecteuler.net에서 자바 스크립트를 사용하여 수학적 문제를 풀려고합니다. 2 백만 미만의 모든 소수의 합을 구하는 것입니다. 내가 작성한 스크립트를 실행하면 브라우저가 다운됩니다 (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); 

스크립트는 작은 숫자에 대한 잘 작동 (내가 < 100000). 그게 뭐가 잘못 되었 니? 어떻게 해결할 수 있습니까? 당신의 도움을 주셔서 감사합니다.

Answer 1

기능 isPrime 수행하는 각 N (당신이 요인으로 총리 이하 모든 단일 번호를 확인하기 때문에) 당신이 확인을 위해 N 모듈로 작업. about one in every seven numbers is prime이라고 가정하면 코드 조각에서 isPrime 기능을 약 28,000 회 수행하고 있음을 의미하며 the modulo operation about 392 million times을 수행하고 있음을 의미합니다. 아마도 자바 스크립트 엔진이 무한 루프에 들어간 것으로 가정하기 때문에 Chrome이 다운되고 있습니다.

NullUserException 말했듯이, there are better ways of finding primes.

본래의 개선에만 제곱근보다 작은 그 숫자의 요소를 확인하는 것입니다. A = B * C, 당신은 하나 B 또는 C이 의 제곱근보다 작은 것으로 가정 할 수있는 모든 수 하십시오. 숫자가 소수가 아님을 알기위한 하나의 요소 만 알아야하기 때문에 제곱근보다 작은 요인을 찾아야합니다. 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 만개까지 작동 할 지 모르겠습니다.

Answer 2

가 당신보다 훨씬 빠른 알고리즘을 사용하고는 2M 번호와 충돌하지 않는,이 기능을 사용 해보세요 : 나는 VB 코드 here로 발견

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

, 난 그냥 자바 스크립트로 변환 .