LoginSignup
0
0

More than 1 year has passed since last update.

@soichirowada(和田 宗一郎)

Prime Numbers Finderを作ってみました

Last updated at Posted at 2022-04-25

Prime Numberとは？

prime numberとは、素数のことです。0と1は含まず、2以上の整数になりますが、1とその数自身でしか割り切れない数をプライムナンバー（素数）と呼びます。

何で？

なぜ作ってみたかといいますと、NHKの再放送でリーマン予測についての番組を見たのですが、何となく影響されて、「JavaScriptで書いたら、Prime Numberをどのくらいのスピードでピックアップできるのかな？」と思い作ってみました。

解説

できるだけ軽く動作するようにするため、下記のような方針でコーディングしました。（isPrimeNumberファンクションについての説明です）

  1. 2より小さな数は素数ではありませんので、falseを返します。
  2. 2 ~ 100の整数については、入力値と2 ~ 100の間の素数を持つsmallPrimeNumbersアレイをマッチングさせ、素数判定を行います。また、素数として認識された数は、一つずつ、グローバルスコープ上にあるprimeNumbersArrayに格納されていきます。
  3. 上記1～2の判定方法に当てはまらない数については、プログラム上にハードコーディングされている2 ~ 97の素数で順番に割っていきます。この場合、割り算の対象となっている数は、すでに2 ~ 100の素数である可能性はありませんので、割り切れた段階でfalseとなります。
  4. さらに、上記の1～3すべてに当てはまらない数については、ループ処理（for loop）に放り込んで、primeNumbersArrayの97の次の素数である101から順番に呼び出して、割り算の余りを確認します。また、その際の割る数については、割られる方の数の平方根を上限値とします。もし、ループ処理の途中で余りが0となった場合は、素数ではありませんので、その時点でfalseとしてリターンします。また、最後まで余りが0とならない場合は、素数となります。

ヒント
1より大きな整数において、「素数ではない数は、素数の掛け算で表現できる」という特徴があります。
4番のループ計算において、割る数については、割られる方の数の平方根を上限値としていますが、実際にはその数自身の平方根よりも大きな素数で割り切れる場合もあります。ただし、その場合は、同時に、その平方根よりも小さな素数で割り切れます。

そのため、割り算を行う際の割る数については、平方根を超える大きな数で割り算しても意味がありません。
例えば、23x29=667のような場合、平方根である25.826...よりも大きな29で割り切れますが、必ず、同時に平方根よりも小さな素数（この場合は23）で割り切れるため、平方根までの割り算で完全に調べることができます。

処理速度

もちろん、PCの処理能力、メインメモリの容量などによって早くなったり遅くなったりしますので、目安にしかなりませんが、私のボロPCの場合、下記のようになりました。
検出する範囲が100万を超えるあたりから、急速に遅くなります。。

1.　2 ~ 100（百）：0.3ミリ秒 => prime numbers 25
2.　2 ~ 1000（千）：0.5ミリ秒 => prime numbers 168
3.　2 ~ 10000（万）：3.9ミリ秒 => prime numbers 1229
4.　2 ~ 100000（十万）：9.8ミリ秒 => prime numbers 9592
5.　2 ~ 1000000（百万）：63ミリ秒 => prime numbers 78498
6.　2 ~ 10000000（千万）：1284ミリ秒（1.28秒） => prime numbers 664579
7.　2 ~ 100000000（億）：29223ミリ秒（29.2秒） => prime numbers 5761455

実行イメージ

Document - Google Chrome 2022_05_06 18_06_42.png

既知の素数

答え合わせに利用できます。例えば、10000までの素数は1229となります。
How many primes are there_ - Google Chrome 2022_05_05 21_14_12.png

サンプルコード

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">

    <title>Document</title>
    <style>
        body {
            padding-left:10px;
            font-family: Arial, Helvetica, sans-serif;
        }
        div {
            margin-top:30px;
            width: 90%; 
        }
        div.primeNumbers{
            white-space: normal;
        }
        div h1, div h4, div .primeNumbers{
            margin-top:-10px;
        }
        .caption, #elapse2 {
            display:none;
        }
        .dark {
            background-color:#00001a;
            color:#00ffff;
        }
        .form input{
            height:25px;
            width:300px;
            font-size: 18px;
            text-align: right;
        }
        .form label{
            font-size: 18px;
        }
        .form button{
            font-size: 18px;
            height:31px;
            width:100px;
            margin-left:5px;
        }
        #submit{
            margin-top:-20px;
        }
        #numberDisplay{
            margin-right:60%;
            margin-left:2%;
            text-align: right;
            font-size: 50px;
            padding-right:10px;
        }

    </style>
</head>
<body class="normal" id="bodyStyle">

    <h1 onClick="changeColor()">Prime Numbers Finder</h1>

    <p id="message">PCの性能によっては、10000000（1千万）以上の上限値を設定すると、非常に長い時間がかかる場合があります。</p>

    <form class="form" id="form1">
        <label for="maxN">上限値</label>
        <input type="number" id="maxNumber" name="maxN" onkeyup="keyCode(event)">
        <button type="submit" onclick="primeNumberFinder()" id="submit">Submit</button>
        <button type="reset" onclick="clearText()">Clear</button>
    </form>

    <h1 id="numberDisplay"></h1>

    <div>
        <p class="caption">プライムナンバーの個数</p>
        <h1 id="count"></h1>
        <p class="caption">計算時間（milli-second）</p>
        <h4 id="elapse"></h4>
        <h4 id="elapse2" style="color:gray"></h4>
        <p class="caption">プライムナンバー</p>
        <div class="primeNumbers">
            <p id="showPrimeNumbers"></p>
        </div>
    </div>   

    <script>

    function keyCode (event) {
        if (event.code === "Delete"){
            clearText();
        } else if (event.code === "Space"){
            clearText();
        }
        const str = document.getElementById('maxNumber').value;
        const numbered = Number(str);
        const formatted = numbered.toLocaleString('en-US');
        document.getElementById('numberDisplay').innerHTML = formatted;
        const strArray = str.split('');
        
        if (Number(str)>0 && strArray.length >= 9) {
            document.getElementById('numberDisplay').style.backgroundColor = "red";
            document.getElementById('numberDisplay').style.color = "white";
        } else if (Number(str)>0 && strArray.length >= 8) {
            document.getElementById('numberDisplay').style.backgroundColor = "magenta";
            document.getElementById('numberDisplay').style.color = "white";
        } else if (Number(str)>0 && strArray.length >= 7) {
            document.getElementById('numberDisplay').style.backgroundColor = "yellow";
            document.getElementById('numberDisplay').style.color = "black";
        } else {
            document.getElementById('numberDisplay').style.backgroundColor = "white";
            document.getElementById('numberDisplay').style.color = "black";
        }
    }

    let primeNumbersArray = [];
    let start = 0;

    function isPrimeNumber (integer) {

        //2より小さい数は全てfalseを返す
        if (integer < 2) return false;

        //100より小さい、かつ100以下のプライムナンバーに合致する数について、trueを返す
        const smallPrimeNumbers = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
        if (integer < 100 && smallPrimeNumbers.includes(integer)) return true;

        //上記の2パターンの選別方法に合致しない場合は、2以上のプライムナンバーで割り算して、余りを見る
        if ( integer % 2 === 0 ) {
            return false;
        } else if ( integer % 3 === 0 ){
            return false;
        } else if ( integer % 5 === 0 ){
            return false;
        } else if ( integer % 7 === 0 ){
            return false;
        } else if ( integer % 11 === 0 ){
            return false;
        } else if ( integer % 13 === 0 ){
            return false;
        } else if ( integer % 17 === 0 ){
            return false;
        } else if ( integer % 19 === 0 ){
            return false;
        } else if ( integer % 23 === 0 ){
            return false;
        } else if ( integer % 29 === 0 ){
            return false;
        } else if ( integer % 31 === 0 ){
            return false;
        } else if ( integer % 37 === 0 ){
            return false;
        } else if ( integer % 41 === 0 ){
            return false;
        } else if ( integer % 43 === 0 ){
            return false;
        } else if ( integer % 47 === 0 ){
            return false;
        } else if ( integer % 53 === 0 ){
            return false;
        } else if ( integer % 59 === 0 ){
            return false;
        } else if ( integer % 61 === 0 ){
            return false;
        } else if ( integer % 67 === 0 ){
            return false;
        } else if ( integer % 71 === 0 ){
            return false;
        } else if ( integer % 73 === 0 ){
            return false;
        } else if ( integer % 79 === 0 ){
            return false;
        } else if ( integer % 83 === 0 ){
            return false;
        } else if ( integer % 89 === 0 ){
            return false;
        } else if ( integer % 97 === 0 ){
            return false;
        } else {
            for (let i = 24, s = Math.sqrt(integer); primeNumbersArray[i] <= s; i++) {
                if (integer % primeNumbersArray[i] === 0) return false;
            }
        }

        return true;
    }

    function primeNumberFinder () {

        primeNumbersArray = [];
        const limitString = document.getElementById('maxNumber').value;
        const limit = Number(limitString);

        if ( limit >= 10**9 ) {
            if (confirm("20分以上かかる可能性がありますが、よろしいですか？")){
                start = performance.now();
                console.time();
                loopFinder();
            } else {
                clearText();
            }
        } else if ( limit >= 10**8 ) {
            if (confirm("30秒以上かかる可能性がありますが、よろしいですか？")){
                start = performance.now();
                console.time();
                loopFinder();
            } else {
                clearText();
            }
        } else {
            start = performance.now();
            console.time();
            loopFinder();
        }

        function loopFinder() {
            for (let i = 2; i <= limit; i++) {
                if (isPrimeNumber(i) === true) {
                    primeNumbersArray.push(i);
                }
            }
        }

        writer();
    }

    function writer () {
        event.preventDefault();
        console.timeEnd();
        const end = performance.now();
        const subtraction = end - start;
        const subtraction2 = millisToMinutesAndSeconds(subtraction);
        subtraction > 1000 ? document.getElementById("elapse2").style.display = "block" : null;

        document.getElementsByClassName("caption")[0].style.display = "block";
        document.getElementsByClassName("caption")[1].style.display = "block";
        document.getElementsByClassName("caption")[2].style.display = "block";
        document.getElementById("count").innerText = primeNumbersArray.length;
        const primeNumbers = primeNumbersArray.join();
        const spaced = primeNumbers.replaceAll(',', ', ');
        document.getElementById("showPrimeNumbers").innerHTML = spaced;
        document.getElementById("elapse").innerText = subtraction;
        document.getElementById("elapse2").innerText = subtraction2;
    }

    function millisToMinutesAndSeconds(millis) {
        const hours = Math.floor(millis / 3600000); 
        const minutes = Math.floor((millis % 3600000) / 60000);
        const seconds = Math.floor((millis % 60000) / 1000);
        const milliSeconds = Math.floor(millis % 1000);
        return hours + "時間" + minutes + "分" + (seconds < 10 ? '0' : '') + seconds + "秒" + milliSeconds + "ミリ秒";
    }

    function clearText () {
        event.preventDefault();
        primeNumbersArray = [];
        start = 0;
        document.getElementById("maxNumber").value = "";
        document.getElementById("numberDisplay").innerHTML = "";
        document.getElementById("count").innerHTML = "";
        document.getElementById("showPrimeNumbers").innerHTML = "";
        document.getElementById("elapse").innerHTML = "";
        document.getElementById("elapse2").innerHTML = "";
        document.getElementById("elapse2").style.display = "none";
        document.getElementsByClassName("caption")[0].style.display = "none";
        document.getElementsByClassName("caption")[1].style.display = "none";
        document.getElementsByClassName("caption")[2].style.display = "none";
        document.getElementById('maxNumber').style.backgroundColor = "white";
        document.getElementById('maxNumber').style.color = "black";
        document.getElementById("maxNumber").focus();
        console.clear();
    }

    function changeColor () {
        let className = document.getElementById("bodyStyle").className;
        console.log(className)
        if (className === "normal") {
            document.getElementById("bodyStyle").className = "dark"
        } else {
            document.getElementById("bodyStyle").className = "normal";
        }
    }

    </script>
</body>
</html>
0
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0