如何在輸入的數字範圍中查找素數

我只是試圖找到輸入的數字範圍的素數。我不知道如何計算尋找素數。我需要將它們添加到數組並在之後輸出數組。我爲計算放了一個佔位符......我似乎無法弄清楚如何找到素數。如何在輸入的數字範圍中查找素數

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" 
    "http://www.w3.org/TR/html4/loose.dtd"> 

<html> 

    <head> 
     <meta http-equiv="content-type" content="text/html; charset=utf-8" /> 

     <title>LeapYears</title> 

     <script type="text/javascript"> 
     /* <![CDATA[ */ 

     function calcPrimeNumber(){ 

       var beginNum = document.numbers.firstNum.value; 
       var endNum = document.numbers.secondNum.value; 
       var primeNumbs = new Array(); 


       var ctr = 0; 
       while (beginNum <= endNum){ //throwaway 
        if ((beginNum % beginNum == 0) && (beginNum % 1 == 0)){ 
         primeNumbs[ctr] = beginNum; 
         ++ctr; 
        } 

        ++beginNum; 
       } 

       if (primeNumbs == 0){ 
        window.alert("There were no leap years within the range."); 
       } 

       else { 
        outputPrimeNums(primeNumbs); 
       } 

     } 

     function outputPrimeNums(primes){ 
      document.write("<h2>Prime Numbers</h2>"); 
      for (i=0;i<primes.length;i++){ 
        document.write(primes[i] + "<br/>"); 
       } 

     } 


     /* ]]> */ 
     </script> 


    </head> 


    <body> 
     <form name="numbers"> 

      Beginning Number: <input type="text" name="firstNum" /> End Number: <input type="text" name="secondNum" /> 
      <input type="button" value="Find Prime Numbers" onclick="calcPrimeNumber()" /> 

     </form> 

    </body> 


</html>

來源

2014-02-15 user3027217

我怎麼會發現在輸入範圍內的素數，如果它不從0開始？ – user3027217

@ user3027217你有沒有試過我的回答 –

嘗試素無示例的這一整版

<html> 

    <head> 
     <meta http-equiv="content-type" content="text/html; charset=utf-8" /> 

     <title>LeapYears</title> 

     <script type="text/javascript"> 
     /* <![CDATA[ */ 

     function calcPrimeNumber(){ 

       var beginNum = parseInt(document.numbers.firstNum.value); 
       var endNum = parseInt(document.numbers.secondNum.value); 
       var primeNumbs = new Array(); 


       var ctr = beginNum; 
       while(ctr<=endNum) 
       { 
        if(isPrime(ctr)==true) 
        { 
         primeNumbs[primeNumbs.length] = ctr; 
        } 
        ctr = ctr+1; 

       } 

       if (primeNumbs.length == 0){ 
        document.getElementById('output_content').innerHTML = "There were no prime no within the range."; 
       } 

       else { 
        outputPrimeNums(primeNumbs); 
       } 

     } 

     function isPrime(num) 
     { 
      var flag = true; 
      for(var i=2; i<=Math.ceil(num/2); i++) 
      { 
       if((num%i)==0) 
       { 
        flag = false; 
        break; 
       } 
      } 
      return flag;  
     } 

     function outputPrimeNums(primes){ 
      var html = "<h2>Prime Numbers</h2>"; 
      for (i=0;i<primes.length;i++){ 
        html += primes[i] + "<br/>"; 
       } 
      document.getElementById('output_content').innerHTML = html; 
     } 


     /* ]]> */ 
     </script> 


    </head> 


    <body> 
     <form name="numbers"> 

      Beginning Number: <input type="text" name="firstNum" /> End Number: <input type="text" name="secondNum" /> 
      <input type="button" value="Find Prime Numbers" onclick="calcPrimeNumber()" /> 

     </form> 
     <div id="output_content"> 
     </div> 
    </body> 


</html>

來源

2014-02-15 09:37:35

你應該使用一些算法來檢查沒有給出是否是素數沒有或沒有內部while循環。 http://en.wikipedia.org/wiki/Prime_number

http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

來源

2014-02-15 09:15:20 john

wikibook頁面是不好的建議，對不起。 :)代碼有可怕，而且非常慢。它顯示了對於1毫升以下的素數5.6秒的時間，但[這個SO回答]（http://stackoverflow.com/a/2068548/849891）在最快的平面Python代碼0.07秒。沒錯，即使在不同的電腦上，速度也快了80倍。 –

這意味着你認爲有人應該爲這個簡單的任務編寫代碼。檢查給定的否是否爲素數。以上代碼的運行時間標記爲答案。 – john

我不是OP，我不可能將答案標記爲已接受。 :)這只是爲了做OP。 :) –

你需要在這裏兩個環路 - 第一個beginNum和endNum和第二之間運行，從1到beginNum運行在外環 beginNum的每個值。

嘗試用以下代碼替換代碼的主要部分。（爲了清楚起見，我將引入一個新的變量 - numberBeingTested）

var ctr = 0; 
var numberBeingTested = beginNum; 

while (numberBeingTested <= endNum){ //throwaway 

    var testDivisor = 2; 
    var isPrime = true; 

    while (testDivisor < numberBeingTested){ //throwaway 
     if (numberBeingTested % testDivisor == 0) { 
      isPrime = false; 
     }      

    ++testDivisor; 
    } 

    if (isPrime){ 
     primeNumbs[ctr] = numberBeingTested; 
     ++ctr; 
    } 

    ++numberBeingTested; 
}

注意，有很多可能的改進，在這裏 - 一開始，這個代碼，因爲它代表會告訴你，1是素數，並且有很大的可能的性能改進（例如測試可能的除數，直到被測數字的平方根而不是數字本身） - 但爲了您的目的，它可能就足夠了。

來源

2014-02-15 09:20:45

謝謝，你說得很清楚。 – user3027217

我嘗試的是從linked question編輯Sieve of Atkin algorithm：

function getPrimes(min, max) { 
    var sieve = [], i, j, primes = []; 
    for (i = 2; i <= max; ++i) { 
     if (!sieve[i]) { 
      // i has not been marked -- it is prime 
      if (i >= min) { 
       primes.push(i); 
      } 
      for (j = i << 1; j <= max; j += i) { 
       sieve[j] = true; 
      } 
     } 
    } 
    return primes; 
} 

console.log(getPrimes(10, 100));

這會給你陣列素數從min到max。它仍然需要從2開始通過所有的數字，所以也許會有更有效的方法來實現這個目標。

來源

2014-02-15 09:28:44

這不是阿特金的篩子，而是埃拉託斯特尼斯的篩子。 :)'j = i << 1'位是*'快速將'i'乘以2「的方式*，但是它是從'i^2'開始工作的非常緩慢的方式。 –

如何在輸入的數字範圍中查找素數

回答

相關問題