しょうすうを判別する


問題を解決するときは思ったよりよく使うので、整理することにしました.
Hyunho NOHのブログ参照.
原理は以下の通りである.検証する半分以上の数を検証する必要はありません.たとえば、確認する数字が14の場合、7より大きい8、9、10、11、12は決して半分ではありません.
14÷7=2... 014\div 7 = 2 ...\014÷7=2... 0
14÷8=1... 614\div 8 = 1 ...\614÷8=1... 6
1)2が除かない場合
確認する 数値2 大きい 数×2>OK 数値{確認する数値より大きい2より大きい}次2>確認する数値2 数値 大きい 数×2>OK 数値
2)3取れない場合
確認する 数字3 大きい 数×3>OK 数字{確認する数字より大きい数字3より大きい}次3>確認する数字3 数値 大きい 数×3>OK 数値
...
N)Nsqrt NN、離れない場合
確認する 数字Nがより大きい 大きい 数×N>チェックする 数値{確認する数値より大きいoversqrt N}大きい回数sqrt N>確認する数値N 数値 大きい 数×N>チェックする 数値
したがって,最後の検査はNsqrt NNまで行うだけである.
ソースコード
function isPrime(n) {
    if (n <= 1) {   // 1
        return false;
    }
    if (n === 2 || n === 3) {   // 2 or 3
        return true;
    }
    if (n % 2 === 0) {  // 2 * K
        return false;
    }
    let divisor = 3;
    let limit = Math.sqrt(n);   // 제곱근까지 반복문
    while (limit >= divisor) {  // 제곱근 >= 3
        if (n % divisor === 0) {    // 3,5,7,...의 배수인 경우
            return false;
        }
        divisor += 2;
    }
    return true;
}
  • 1でfalseが返されます.
  • 2、3の場合trueを返します
  • 偶数の場合はfalseを返します.
  • Nsqrt NNは、3から切り離すことができればfalseを返します.
    4-1. 分けた数はすべての偶数を除外しているので,それぞれ+2を与える.
  • 適用されない場合はtrue
    一般的に検査の回数は2であるのに対し,このようにすると演算回数が少なくなり,より有利になると予想される.😁