整数が素数であるかどうかをテストします。

Question

isPrime::Integer->Bool 
isPrime n=not (hasfactor n 2(div n 2)) 

hasfactor::Integer->Integer->Integer->Bool 
hasfactor n low high 
    |low>high=False 
    |mod n low==0=True 
    |otherwise = hasfactor n (low+1) high 

2行目以外のほとんどのコードは、not (hasfactor n 2(div n 2))です。なぜ上限は(div n 2)ですか？ test 8と入力した場合、(hasfactor n 2(div n 2))はhasfactor 8 2 4となりますが、ここでは8を分割する点はありません。

Answer 1

ここでは、整数の最小素因数が2であるため、最大は最大でn/2になるという事実を利用しています。

より良いアルゴリズムは、因子があるかどうかを見つけるために、sqrt（n）までの数字をチェックします。あなたは

UPDATE

nまでの短絡（n）の平方根とのチェックに非プライムのような特殊なケースとして1を処理する必要があるものの、この

prime n = null [ k | k <- [2..n], k*k <= n, mod n k == 0 ] 

よう

何か素数の場合、これはより良いアプローチかもしれません。