intime o'

私はこねることのできる粘土でしかなかったが、鋳型を拒否する粘土だった(サガン著「悲しみよ こんにちわ」より) 素数の判定。ラン択 - JavaScript 2011/09/03(Sat.)

自然数nに対してk回「nが合成数であるか」の実験をして素数判定するやつ。
合成数を合成数と判断する確率は 1-(1/4)^k らしいよ。

自然数nが素数か判定するテスト。kは試行回数。もちろん多い方がいい。
n: 
k:  

n is a Natural number.
k is 100 as example.
while(k--){
	a is an integer less than n.
	which is chosen randomly.
	if(GCD(n, a)≠1)n is 合成数, and exit this program.
	if(a n-1≢1 mod n){
		n is 合成数(∵Fermat's little theorem),
		and exit this program.
	}
}
(Not yet this program is running,)
n may be thought as 素数.

コメ(0) | トラ(0)

---