素数テストの問題点

Question

私は初心者で素数テストを完了しようとしていますが、問題が発生しています。ここで私が持っているものです。

var n = Number(prompt("Input the number you want to check for prime:")); 
var i; 


if (n < 2) { 
    alert(n + " is not a prime number."); 
} 
for (var i = 2; i <= Math.sqrt(n); i++) { 
    if (n % i === 0) { 
     alert(n + " is not a prime number."); 
     break; 
    } 

    else { 
     alert(n + " is a prime number."); 
     break; 
    } 
} 

その中に3とI入力3または2と任意の番号が「それはにISN場合でも素数として戻って来ている場合には、アラートを除いて正常に動作していますがポップアップ表示されません。 t。それ以外は私のテストのすべてがうまくいっています。

Answer 1

に尋ねた古い質問への参照を持っていてください。チェックが完了したかどうかにかかわらず、あなたは壊れています。

var n = Number(prompt("Input the number you want to check for prime:")); 
var i; 
var isPrime = true; 

if (n < 2) { 
    isPrime = false; 
} else if (n < 4 && n >= 2) { 
    // isPrime is already true 
} else if (n % 2 === 0) { 
    isPrime = false; // no divisor of 2 can be prime 
} else { 
    var sqrtN = Math.sqrt(n); 
    for (var i = 3; i <= sqrtN; i = i + 2) { 
     if (n % i === 0) { 
      // Only break out of the loop if a match is found 
      isPrime = false; 
      break; 
     } 
    } 
} 
if (isPrime) { 
    alert(n + " is a prime number."); 
} else { 
    alert(n + " is not a prime number."); 
} 

または、おそらくより組織ソリューション：もちろん

function isPrime (n) { 
    n = parseInt(n); 
    var i; 
    if (Number.isNaN(n)) { 
    return false; 
    } else if (n < 2) { 
    // 1 is not prime 
    return false; 
    } if (n < 4) { 
    // 2 and 3 are prime, so why not skip checking them? 
    return true; 
    } else if (n % 2 === 0) { 
    // No number divisible by 2 is prime. 
    return false; 
    } else { 
    // This won't change, so calculate it once as suggested by Weather Vane. 
    var sqrtN = Math.sqrt(n); 
    // 4, 6, 8... All divisible by 2, and would be caught by initial check. 
    for (i = 3; i < sqrtN; i = i + 2) { 
     // Not a prime if it's evenly divisible. 
     if (n % i === 0) { 
     return false; 
     } 
    } 
    // Otherwise prime. 
    return true; 
    } 
} 

Answer 2

var UI = window.prompt("Enter a whole number to test as a prime number: \n", "0"); 
var TV = parseInt(UI, 10); 
var HITS = 0; 
var DD = TV; 
while (DD > 0) { 
    if (TV % DD === 0) { 
     HITS++; 
    } 
    DD--; 
} 

if (HITS > 2) { 
    document.write(UI + " is a NOT prime number"); 
} else { 
    document.write(UI + " is a prime number"); 
} 

ああ、あなたの問題はあなたがループを構造化しました方法ですstackoverflowの link to the old question

Answer 3

。 n % iが0でない場合は、iはnを除外しませんが、nが素数であることを意味しません。あなたはそれを言うためにすべてiをチェックしなければなりません。

また、反復ごとに高価なMath.sqrt(n)を再計算しないでください。 NaNにご注意ください。もちろん

var n = Number(prompt("Input the number you want to check for prime:")); 
 
function isPrime(n) { 
 
    if (n < 2 || !n) return false; 
 
    for (var i = 2; i*i <= n; i++) { 
 
    if (n % i === 0) return false; 
 
    } 
 
    return true; 
 
} 
 
alert(n + " is " + (isPrime(n) ? "" : "NOT ") + "a prime number.");

、このアルゴリズムは、（pseudo-polynomial）指数関数的です。大きなnには使用しないでください。代わりに、例えばMiller–Rabin primality testまたはAKS primality testです。これらは多項式です。