デブリ屋

shorの因数分解アルゴリズムが存在する今日、
量子コンピューター手に入れることはできないので、いかに素数であるかを条件分岐することが最速だと思われる。
まず簡単に
１、偶数は無視（２は素数なので別処理）
２、整数nの平方根までの整数で剰余判断。
まずはこんなもので、以下（今の私のtwitter bot のプログラムｗ　44211790234832169331これは10¹⁸番目の素数なのだが30秒で強制kill・・・）
これはいけた。3475385758524527　10¹⁴番目16桁。実行時間36.828640937805秒

<br />
&lt;?php<br />
$sum = ＊＊＊＊; //整数n<br />
if($sum%2 == 0){ //0(mod2)の場合<br />
	if($sum==2){ //2の場合<br />
		$mes = $sum . &quot;は素数である。&quot;;<br />
	}else{<br />
		$mes = $sum . &quot;は素数ではない。&quot;;<br />
	}<br />
}else{<br />
	$amari_flag = 0; //余りの有無フラグ0:有1:無<br />
	for($i=3; $i&lt;sqrt($sum); $i+=2){ //3から2づつ加えてのforループ<br />
		if($sum%$i==0){<br />
			$amari_flag = 1;break; //余り無し、すなわち素数ではないことを表すフラグ<br />
		}<br />
	}<br />
	if($amari_flag == 0){<br />
		$mes = $sum . &quot;は素数である。&quot;;<br />
	}else{<br />
		$mes = $sum . &quot;は素数ではない。&quot;;<br />
	}<br />
}<br />
?&gt;<br />

今後条件にプラスしていきたいもの
３、メルセンヌ素数　2ⁿ-1　これだと2進数で１１１１１１１・・・・・の形を現す。
４、フェルマーの小定理　a^p-1 ≡ 1 (mod p)
５、自然数は、6n-1、6n、6n+1、6n+2、6n+3、6n+4で表せる、
　ここで、6、6n+2、6n+3、6n+4は明らかに素数ではない
　5以上の素数は6n+1、6n-1で表せる。
　(6n±1)^2>=36n²±12n+1=12(3n²±n)+1≡1(mod12)

以上などを条件に組み込み高速化できないかを、できたらやっていこう・・・
一般の整数に対する判定法：APR-CL、ECPP、AKSなども調べていきたいです。
個人的にはフェルマーの小定理あたりが食いつきたいところですね。中国人の剰余定理とかも絡ませたいわ～