Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件

# はじめに
以下の自分の記事で自作の素数判定（素因数分解）プログラムを公開したのだが，こうしたほうがもっと速いんじゃね？という添削指導が入った。

[【京大2021】3ⁿ－2ⁿが素数ならnも素数になることを示せ - Qiita](https://qiita.com/TETSURO1999/items/dd7f5358986844de5ea8)
[【京大2021】pが素数ならばp⁴＋14が素数ではないことを示せ - Qiita](https://qiita.com/TETSURO1999/items/6dc0d77f683b66674360)

まずは自作のコード（一部抜粋）を示す。
このプログラムのキモは，与えられた自然数の約数を検索する `search_divisor()` 関数である。与えられた自然数に対し既知の素数リスト内に割り切れるものがあればそれが約数であり，ここで検索が終了するが，見つからなかった場合，素数リストの最大値（奇数）に２を加えた奇数を新たな約数の候補とし，この候補が素数であることを `search_divisor()` を呼び出してチェックする。もしも約数候補が素数でなければ，試し割りを行わない。素数であれば素数リストに末尾に追加して，与えられた自然数が割り切れるかどうか確認する。割り切れればそれが約数であり，検索を終了する。割り切れなければ，さらに２を加えた奇数を新たな約数の候補として繰り返す。

```javascript
//------------------------------------------------------------------------------
// 100 以下の素数リスト
//------------------------------------------------------------------------------
var	list = [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];
//------------------------------------------------------------------------------
// 約数を検索する
// ・素数の場合は 1 を返す
// ・合成数の場合は 1 より大きい最小の約数を返す
//------------------------------------------------------------------------------
function search_divisor( n ) {
	var	m;
	//--------------------------------------------------------------------------
	// 素数リストをチェックする
	//--------------------------------------------------------------------------
	for( var i = 0; i < list.length; i++ ) {
		m = list[i];
		if( m * m > n ) return( 1 );
		if( n % m == 0 ) return( m );
	}
	//--------------------------------------------------------------------------
	// 約数の候補を探す
	//--------------------------------------------------------------------------
	for(;;) {
		m += 2;
		if( m * m > n ) return( 1 );
		if( search_divisor( m ) != 1 ) continue;
		list.push( m );
		if( n % m == 0 ) return( m );
	}
}
//------------------------------------------------------------------------------
// 素因数分解を行う
//------------------------------------------------------------------------------
function prime_factorize( p ) {
	var	a = [];
	for( var q; ( q = search_divisor( p ) ) > 1; p = p / q )
		a.push( q );
	a.push( p );
	return( a );
}
```

<details><summary>長いので全コードはコチラ</summary>
WSH（Windows Script Host）で動かす javascript プログラムなので Windows ユーザなら誰でもコマンドプロンプト上で動かせる。

```javascript:checkprime.js
//------------------------------------------------------------------------------
// 素数チェックおよび素因数分解を行います。
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
// 100 以下の素数リスト
//------------------------------------------------------------------------------
var	list = [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];
//------------------------------------------------------------------------------
// 約数を検索する
// ・素数の場合は 1 を返す
// ・合成数の場合は最小の約数を返す
//------------------------------------------------------------------------------
function search_divisor( n ) {
	var	m;
	//--------------------------------------------------------------------------
	// 素数リストをチェックする
	//--------------------------------------------------------------------------
	for( var i = 0; i < list.length; i++ ) {
		m = list[i];
		if( m * m > n ) return( 1 );
		if( n % m == 0 ) return( m );
	}
	//--------------------------------------------------------------------------
	// 約数の候補を探す
	//--------------------------------------------------------------------------
	for(;;) {
		m += 2;
		if( m * m > n ) return( 1 );
		if( search_divisor( m ) != 1 ) continue;
		list.push( m );
		if( n % m == 0 ) return( m );
	}
}
//------------------------------------------------------------------------------
// 素因数分解を行う
//------------------------------------------------------------------------------
function prime_factorize( p ) {
	var	a = [];
	for( var q; ( q = search_divisor( p ) ) > 1; p = p / q )
		a.push( q );
	a.push( p );
	return( a );
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main( args ) {
	//--------------------------------------------------------------------------
	// オプション解析
	//--------------------------------------------------------------------------
	if( args.Count == 0 ) {
		WScript.Echo( "素数のチェック，合成数の場合は素因数分解を行います。" );
		WScript.Echo( "" );
		WScript.Echo( "CHECKPRIME(.JS) [整数]" );
		WScript.Echo( "" );
		WScript.Echo( "素数の場合は 0，合成数の場合は 1 を返します。" );
		return( -1 );
	}
	var	n = parseInt( args(0) );
	if( n < 2 ) {
		WScript.Echo( "2 以上の整数を入力して下さい!!" );
		return( -1 );
	}
	//--------------------------------------------------------------------------
	// 素因数分解を行う
	//--------------------------------------------------------------------------
	var	a = prime_factorize( n );
	if( a.length == 1 ) {
		WScript.Echo( "整数 " + n + " は素数です。" );
		return( 0 );
	} else {
		WScript.Echo( "整数 " + n + " は合成数です。" );
		WScript.Echo( a.join(",") + " を素因数に持ちます。" );
		return( 1 );
	}
}
var	ret = main( WScript.Arguments.Unnamed );
try {
	WScript.Quit( ret );
} catch(e) {
	/* 何もしない */
}
```
</details>

# どこが遅いのか？
このプログラムはもともと大学入試問題で取り扱う程度の素数を判定（もしくは素因数分解）するために作られたので $100$ 以下の素数リストを内蔵しており，$100^2 = 10000$ 以下の自然数までならば高速に素数判定できる。

しかし，これらを超えてしまうと一気に計算時間がかかるようになる。計算時間を実測した結果を以下に示す。素数の大きさが1000倍になると計算時間は100倍になり，綺麗に $O(N^{2/3})$ のラインに乗っている。普通[^脚注1]に作っても $O(N^{1/2})$ なのでかなり頭の悪いアルゴリズムといえよう。

[^脚注1]: [素数判定アルゴリズムいろいろ - Qiita](https://qiita.com/ppza53893/items/e0f464340d6f97760cd5)

```plantuml
@startuml
<style>
footer {
  fontColor black
  fontSize 16
}
</style>
footer 図１　素数判定に要した時間
title <img https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/7f7d458c-b97e-040e-bf7e-ad63590ce5e1.png>
@enduml
```

<details><summary>測定時間の詳細はコチラ</summary>
<table>
<caption>表１　素数判定に要した時間</caption>
<thead>
<tr><th style="text-align:center;">素数</th>
    <th style="text-align:center;">時間（秒）</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right;">1,250,000,000,111</td>
    <td style="text-align:right;">3.940</td></tr>
<tr><td style="text-align:right;">2,500,000,000,009</td>
    <td style="text-align:right;">6.050</td></tr>
<tr><td style="text-align:right;">5,000,000,000,053</td>
    <td style="text-align:right;">9.460</td></tr>
<tr><td style="text-align:right;">10,000,000,000,037</td>
    <td style="text-align:right;">14.930</td></tr>
<tr><td style="text-align:right;">20,000,000,000,021</td>
    <td style="text-align:right;">22.790</td></tr>
<tr><td style="text-align:right;">40,000,000,000,001</td>
    <td style="text-align:right;">36.020</td></tr>
<tr><td style="text-align:right;">80,000,000,000,027</td>
    <td style="text-align:right;">56.620</td></tr>
<tr><td style="text-align:right;">160,000,000,000,069</td>
    <td style="text-align:right;">91.540</td></tr>
<tr><td style="text-align:right;">320,000,000,000,029</td>
    <td style="text-align:right;">146.120</td></tr>
<tr><td style="text-align:right;">640,000,000,000,033</td>
    <td style="text-align:right;">234.660</td></tr>
</tbody>
</table>
</details>

さて，どこが問題点なのかというと，試し割りの回数を節約するため，約数候補の素数チェックを行っていることである。素数チェックの中では約数候補 $m$ が素数であることを確認するため素数リストにある $\sqrt{m}$ 以下の素数で試し割りを行っており，すべて割り切れなかった場合に $m$ が素数と判断される。

素数定理[^脚注2]より，$\sqrt{m}$ 以下の素数の数はおよそ $\sqrt{m}/\log{\sqrt{m}}$ であるから，試し割りを１回節約するつもりが，逆に大幅に増えていたことになる。

[^脚注2]: [素数定理 - Wikipedia](https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%AE%9A%E7%90%86)

# 具体的な添削内容

具体的な添削内容を以下に示す。元のコードに比べて随分とすっきりしている。

これは約数の候補 $q$ が素数であろうと合成数であろうと気にせず，どんどん試し割りしていこうという方式だ。さすがに $4$ とか $6$ とか偶数でも試し割りするのは如何なものかと思うが，コチラのほうが桁違いに速くなる。

なおオリジナルの添削コードではループ条件を `q <= Math.sqrt(p)` としていたが，時間のかかる平方根計算を避けて `q * q <= p` と修正した。※ちょっとだけ速くなった。

```javascript
//------------------------------------------------------------------------------
// 素因数分解を行う（添削指導後）
//------------------------------------------------------------------------------
function prime_factorize( p ) {
	var	a = [];
	for( var q = 2; q * q <= p; q++ ) {
		while( p % q == 0 ) {
			p /= q; a.push( q );
		}
	}
	if( p > 1 ) a.push( p );
	return( a );
}
```

プログラムがすっきりすると改善点が分かり易くなる。先に $2$ で試し割りを終えて，その後は奇数のみ試し割りを行うようにするとさらに２倍速くなる。

```javascript
//------------------------------------------------------------------------------
// 素因数分解を行う（添削指導後＋奇数サーチ）
//------------------------------------------------------------------------------
function prime_factorize( p ) {
	var	a = [];
	while( p >= 2 && p % 2 == 0 ) {
		p /= 2; a.push( 2 );
	}
	for( var q = 3; q * q <= p; q += 2 ) {
		while( p % q == 0 ) {
			p /= q; a.push( q );
		}
	}
	if( p > 1 ) a.push( p );
	return( a );
}
```

計算時間の比較を示す。添削指導後および奇数サーチは桁違いに速くなっているほか，計算量も理論通り $O(N^{1/2})$ となっていることが分かる。

```plantuml
@startuml
<style>
header {
  fontColor black
  fontSize 14
  horizontalAlignment left
}
footer {
  fontColor black
  fontSize 16
}
</style>
header
<font color=red>●</font>オリジナル　<font color=blue>◆</font>添削指導後　<font color=lime>■</font>奇数サーチ
end header
footer 図２　計算時間の比較
title <img https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/fc19d448-10ca-ad07-2f87-a9ab3b200a7b.png>
@enduml
```

<details><summary>計算時間の比較詳細はコチラ</summary>
<table>
<caption>表２　計算時間の比較</caption>
<thead>
<tr><th rowspan=2 style="text-align:center;">素数</th>
    <th colspan=3 style="text-align:center;">時間（秒）</th></tr>
<tr><th style="text-align:center;">オリジナル</th>
    <th style="text-align:center;">添削指導後</th>
    <th style="text-align:center;">奇数サーチ</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right;">1,250,000,000,111</td>
    <td style="text-align:right;">3.940</td>
    <td style="text-align:right;">0.146</td>
    <td style="text-align:right;">0.100</td></tr>
<tr><td style="text-align:right;">2,500,000,000,009</td>
    <td style="text-align:right;">6.050</td>
    <td style="text-align:right;">0.180</td>
    <td style="text-align:right;">0.117</td></tr>
<tr><td style="text-align:right;">5,000,000,000,053</td>
    <td style="text-align:right;">9.460</td>
    <td style="text-align:right;">0.233</td>
    <td style="text-align:right;">0.145</td></tr>
<tr><td style="text-align:right;">10,000,000,000,037</td>
    <td style="text-align:right;">14.930</td>
    <td style="text-align:right;">0.305</td>
    <td style="text-align:right;">0.183</td></tr>
<tr><td style="text-align:right;">20,000,000,000,021</td>
    <td style="text-align:right;">22.790</td>
    <td style="text-align:right;">0.408</td>
    <td style="text-align:right;">0.236</td></tr>
<tr><td style="text-align:right;">40,000,000,000,001</td>
    <td style="text-align:right;">36.020</td>
    <td style="text-align:right;">0.554</td>
    <td style="text-align:right;">0.311</td></tr>
<tr><td style="text-align:right;">80,000,000,000,027</td>
    <td style="text-align:right;">56.620</td>
    <td style="text-align:right;">0.764</td>
    <td style="text-align:right;">0.420</td></tr>
<tr><td style="text-align:right;">160,000,000,000,069</td>
    <td style="text-align:right;">91.540</td>
    <td style="text-align:right;">1.061</td>
    <td style="text-align:right;">0.570</td></tr>
<tr><td style="text-align:right;">320,000,000,000,029</td>
    <td style="text-align:right;">146.120</td>
    <td style="text-align:right;">1.480</td>
     <td style="text-align:right;">0.785</td></tr>
<tr><td style="text-align:right;">640,000,000,000,033</td>
    <td style="text-align:right;">234.660</td>
    <td style="text-align:right;">2.075</td>
    <td style="text-align:right;">1.094</td></tr>
</tbody>
</table>
</details>

# さらに改善するには？
Wheel Factorization 法[^脚注3]を使えば，奇数サーチのさらに２倍速くなる。ただ，WSH の javascript エンジンはアホの子なので Wheel Factorization 法を使っても速くはならなかった。奇数サーチより僅かに速い程度。ただし，JScript9，Chakra など JIT コンパイラ型のエンジンに切り替えると高速化の効果がはっきり見える。

[^脚注3]: [Wheel Factorizationについて - Qiita](https://qiita.com/ppza53893/items/49e480d22858a449dc69)

```javascript
//------------------------------------------------------------------------------
// 素因数分解を行う（Wheel Factorization）
//------------------------------------------------------------------------------
function prime_factorize( p ) {
	var	a = [];
	while( p >= 2 && p % 2 == 0 ) {
		p /= 2; a.push( 2 );
	}
	while( p >= 3 && p % 3 == 0 ) {
		p /= 3; a.push( 3 );
	}
	while( p >= 5 && p % 5 == 0 ) {
		p /= 5; a.push( 5 );
	}
	var	wheel = [4,2,4,2,4,6,2,6];
	for( var q = 7, i = 0; q * q <= p; q += wheel[i++], i %= 8 ) {
		while( p % q == 0 ) {
			p /= q; a.push( q );
		}
	}
	if( p > 1 ) a.push( p );
	return( a );
}
```

一応，計算結果を載せておく。
<details><summary>Wheel Factorization の比較詳細はコチラ</summary>
<table>
<caption>表３　Wheel Factorization の比較詳細</caption>
<thead>
<tr><th rowspan=2 style="text-align:center;">素数</th>
    <th colspan=4 style="text-align:center;">時間（秒）</th></tr>
<tr><th style="text-align:center;">オリジナル</th>
    <th style="text-align:center;">添削指導後</th>
    <th style="text-align:center;">奇数サーチ</th>
    <th style="text-align:center;">Wheel<br>Factorization</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right;">2,500,000,000,009</td>
    <td style="text-align:right;">6.050</td>
    <td style="text-align:right;">0.180</td>
    <td style="text-align:right;">0.117</td>
    <td style="text-align:right;">0.117</td></tr>
<tr><td style="text-align:right;">5,000,000,000,053</td>
    <td style="text-align:right;">9.460</td>
    <td style="text-align:right;">0.233</td>
    <td style="text-align:right;">0.145</td>
    <td style="text-align:right;">0.143</td></tr>
<tr><td style="text-align:right;">10,000,000,000,037</td>
    <td style="text-align:right;">14.930</td>
    <td style="text-align:right;">0.305</td>
    <td style="text-align:right;">0.183</td>
    <td style="text-align:right;">0.179</td></tr>
<tr><td style="text-align:right;">20,000,000,000,021</td>
    <td style="text-align:right;">22.790</td>
    <td style="text-align:right;">0.408</td>
    <td style="text-align:right;">0.236</td>
    <td style="text-align:right;">0.234</td></tr>
<tr><td style="text-align:right;">40,000,000,000,001</td>
    <td style="text-align:right;">36.020</td>
    <td style="text-align:right;">0.554</td>
    <td style="text-align:right;">0.311</td>
    <td style="text-align:right;">0.307</td></tr>
<tr><td style="text-align:right;">80,000,000,000,027</td>
    <td style="text-align:right;">56.620</td>
    <td style="text-align:right;">0.764</td>
    <td style="text-align:right;">0.420</td>
    <td style="text-align:right;">0.411</td></tr>
<tr><td style="text-align:right;">160,000,000,000,069</td>
    <td style="text-align:right;">91.540</td>
    <td style="text-align:right;">1.061</td>
    <td style="text-align:right;">0.570</td>
    <td style="text-align:right;">0.562</td></tr>
<tr><td style="text-align:right;">320,000,000,000,029</td>
    <td style="text-align:right;">146.120</td>
    <td style="text-align:right;">1.480</td>
    <td style="text-align:right;">0.785</td>
    <td style="text-align:right;">0.775</td></tr>
<tr><td style="text-align:right;">640,000,000,000,033</td>
    <td style="text-align:right;">234.660</td>
    <td style="text-align:right;">2.075</td>
    <td style="text-align:right;">1.094</td>
    <td style="text-align:right;">1.078</td></tr>
</tbody>
</table>
</details>

## JScript9 の結果
WSH の javascript エンジンを JScript9 に切り替えた場合の結果を示す。Wheel Factorization の効果が見えるようになった。なお，素数の大きさが $10^{13}$ を下回ると JIT コンパイラのコンパイル時間によるオーバーヘッドが見えてくる。

```plantuml
@startuml
<style>
header {
  fontColor black
  fontSize 14
  horizontalAlignment left
}
footer {
  fontColor black
  fontSize 16
}
</style>
header
<font color=red>●</font>オリジナル　<font color=blue>◆</font>添削指導後　<font color=lime>■</font>奇数サーチ　<font color=black>×</font>Wheel Factorization
end header
footer 図３　JScript9 の結果
title <img https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/adc595ed-896f-2662-31f6-f8d06b2bee9f.png>
@enduml
```

<details><summary>JScript9 の結果詳細はコチラ</summary>
<table>
<caption>表４　JScript9 の結果</caption>
<thead>
<tr><th rowspan=2 style="text-align:center;">素数</th>
    <th colspan=4 style="text-align:center;">時間（秒）</th></tr>
<tr><th style="text-align:center;">オリジナル</th>
    <th style="text-align:center;">添削指導後</th>
    <th style="text-align:center;">奇数サーチ</th>
    <th style="text-align:center;">Wheel<br>Factorization</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right;">1,250,000,000,111</td>
    <td style="text-align:right;">0.230</td>
    <td style="text-align:right;">0.065</td>
    <td style="text-align:right;">0.049</td>
    <td style="text-align:right;">0.044</td></tr>
<tr><td style="text-align:right;">2,500,000,000,009</td>
    <td style="text-align:right;">0.280</td>
    <td style="text-align:right;">0.075</td>
    <td style="text-align:right;">0.054</td>
    <td style="text-align:right;">0.047</td></tr>
<tr><td style="text-align:right;">5,000,000,000,053</td>
    <td style="text-align:right;">0.420</td>
    <td style="text-align:right;">0.093</td>
    <td style="text-align:right;">0.063</td>
    <td style="text-align:right;">0.053</td></tr>
<tr><td style="text-align:right;">10,000,000,000,037</td>
    <td style="text-align:right;">0.620</td>
    <td style="text-align:right;">0.115</td>
    <td style="text-align:right;">0.075</td>
    <td style="text-align:right;">0.062</td></tr>
<tr><td style="text-align:right;">20,000,000,000,021</td>
    <td style="text-align:right;">0.930</td>
    <td style="text-align:right;">0.149</td>
    <td style="text-align:right;">0.090</td>
    <td style="text-align:right;">0.073</td></tr>
<tr><td style="text-align:right;">40,000,000,000,001</td>
    <td style="text-align:right;">1.480</td>
    <td style="text-align:right;">0.195</td>
    <td style="text-align:right;">0.114</td>
    <td style="text-align:right;">0.089</td></tr>
<tr><td style="text-align:right;">80,000,000,000,027</td>
    <td style="text-align:right;">2.380</td>
    <td style="text-align:right;">0.260</td>
    <td style="text-align:right;">0.146</td>
    <td style="text-align:right;">0.112</td></tr>
<tr><td style="text-align:right;">160,000,000,000,069</td>
    <td style="text-align:right;">3.720</td>
    <td style="text-align:right;">0.352</td>
    <td style="text-align:right;">0.193</td>
    <td style="text-align:right;">0.143</td></tr>
<tr><td style="text-align:right;">320,000,000,000,029</td>
    <td style="text-align:right;">5.660</td>
    <td style="text-align:right;">0.483</td>
    <td style="text-align:right;">0.258</td>
    <td style="text-align:right;">0.189</td></tr>
<tr><td style="text-align:right;">640,000,000,000,033</td>
    <td style="text-align:right;">8.720</td>
    <td style="text-align:right;">0.668</td>
    <td style="text-align:right;">0.349</td>
    <td style="text-align:right;">0.253</td></tr>
</tbody>
</table>
</details>

## Chakra の結果
WSH の javascript エンジンを Chakra に切り替えた場合の結果を示す。Wheel Factorization の効果がよりはっきりと見えるようになった。なお，JIT コンパイラのオーバーヘッドは JScript9 よりも大きい。時間をかけて最適化を図っているものと考えられる。

```plantuml
@startuml
<style>
header {
  fontColor black
  fontSize 14
  horizontalAlignment left
}
footer {
  fontColor black
  fontSize 16
}
</style>
header
<font color=red>●</font>オリジナル　<font color=blue>◆</font>添削指導後　<font color=lime>■</font>奇数サーチ　<font color=black>×</font>Wheel Factorization
end header
footer 図４　Chakra の結果
title <img https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/c45708b0-41c6-3317-869d-966eae71e667.png>
@enduml
```

<details><summary>Chakra の結果詳細はコチラ</summary>
<table>
<caption>表５　Chakra の結果</caption>
<thead>
<tr><th rowspan=2 style="text-align:center;">素数</th>
    <th colspan=4 style="text-align:center;">時間（秒）</th></tr>
<tr><th style="text-align:center;">オリジナル</th>
    <th style="text-align:center;">添削指導後</th>
    <th style="text-align:center;">奇数サーチ</th>
    <th style="text-align:center;">Wheel<br>Factorization</th></tr>
</thead>
<tbody>
<tr>
<td style="text-align:right;">1,250,000,000,111</td>
<td style="text-align:right;">0.180</td>
<td style="text-align:right;">0.122</td>
<td style="text-align:right;">0.079</td>
<td style="text-align:right;">0.054</td></tr>
<tr>
<td style="text-align:right;">2,500,000,000,009</td>
<td style="text-align:right;">0.210</td>
<td style="text-align:right;">0.157</td>
<td style="text-align:right;">0.097</td>
<td style="text-align:right;">0.060</td></tr>
<tr>
<td style="text-align:right;">5,000,000,000,053</td>
<td style="text-align:right;">0.310</td>
<td style="text-align:right;">0.208</td>
<td style="text-align:right;">0.122</td>
<td style="text-align:right;">0.069</td></tr>
<tr>
<td style="text-align:right;">10,000,000,000,037</td>
<td style="text-align:right;">0.480</td>
<td style="text-align:right;">0.278</td>
<td style="text-align:right;">0.157</td>
<td style="text-align:right;">0.084</td></tr>
<tr>
<td style="text-align:right;">20,000,000,000,021</td>
<td style="text-align:right;">0.720</td>
<td style="text-align:right;">0.376</td>
<td style="text-align:right;">0.208</td>
<td style="text-align:right;">0.102</td></tr>
<tr>
<td style="text-align:right;">40,000,000,000,001</td>
<td style="text-align:right;">1.140</td>
<td style="text-align:right;">0.517</td>
<td style="text-align:right;">0.279</td>
<td style="text-align:right;">0.133</td></tr>
<tr>
<td style="text-align:right;">80,000,000,000,027</td>
<td style="text-align:right;">1.770</td>
<td style="text-align:right;">0.715</td>
<td style="text-align:right;">0.376</td>
<td style="text-align:right;">0.172</td></tr>
<tr>
<td style="text-align:right;">160,000,000,000,069</td>
<td style="text-align:right;">2.760</td>
<td style="text-align:right;">0.995</td>
<td style="text-align:right;">0.516</td>
<td style="text-align:right;">0.237</td></tr>
<tr>
<td style="text-align:right;">320,000,000,000,029</td>
<td style="text-align:right;">4.210</td>
<td style="text-align:right;">1.390</td>
<td style="text-align:right;">0.712</td>
<td style="text-align:right;">0.316</td></tr>
<tr>
<td style="text-align:right;">640,000,000,000,033</td>
<td style="text-align:right;">6.890</td>
<td style="text-align:right;">1.950</td>
<td style="text-align:right;">0.994</td>
<td style="text-align:right;">0.416</td></tr>
</tbody>
</table>
</details>

# 備考
WSH の javascript エンジンを JScript9 や Chakra に切り替える方法は下記記事を参照のこと。

[【京大2021】3ⁿ－2ⁿが素数ならnも素数になることを示せ - Qiita](https://qiita.com/TETSURO1999/items/dd7f5358986844de5ea8)

ベンチマーク環境は下記の通り
- OS: Windows10 Pro 2022H2
- CPU: Core i5 10400 2.9GHz
- RAM: 8GB

# 次回
次回に続きます。

- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(2) - Qiita](https://qiita.com/TETSURO1999/items/28ca00f958628423d64f?1)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(3) - Qiita](https://qiita.com/TETSURO1999/items/38ddcc0f4f3411924fe9)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(4) - Qiita](https://qiita.com/TETSURO1999/items/a8321c80405a70755c41)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(5) - Qiita](https://qiita.com/TETSURO1999/items/4957acd1614aa319f787)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(6) - Qiita](https://qiita.com/TETSURO1999/items/a51747cfac9f89b51a11)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(7) - Qiita](https://qiita.com/TETSURO1999/items/392fd3a8f999a018edfd)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(8) - Qiita](https://qiita.com/TETSURO1999/items/599d4b7ccb2b4e407a34)
- [Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(9) 最終回 - Qiita](https://qiita.com/TETSURO1999/items/5d69e183af27487de7bc)

# 謝辞
@fujitanozomu （藤田望）さんご指導ありがとうございました。