70356


Haskellで、値`n`が素数ならば`True`を、素数でなければ`False`を返す関数primeを作成したいのですが、どのようにプログラムしていいのかわかりませんでした。  
最初に要は、値`n`を`2`から`n−1`まで順番に割っていって、最後まで割り切れなければ素数であると判定できるということだと思ったので、以下のようにプログラムしてみました。

[code]

    a>=2　&& a<=n−１
    prime(n,a)=if n`mod`a /= 0 then False else True
    
[/code]

しかし、以下のようなコンパイルエラーが発生しました。

[code]

    [1 of 1] Compiling Main             ( sample1002.hs, interpreted )
    
    sample1002.hs:177:1: error:
        Parse error: naked expression at top level
        Perhaps you intended to use TemplateHaskell
    Failed, modules loaded: none.
    
[/code]

私は、`mod`という表現を使用したのはおそらく正しいと思ったのですが、「`n`を`2`から`n−1`まで割っていったときに、割り切れない」という意味のプログラムの表現方法が間違っているのだと考えました。（自分は、それを表現するために、`2`以上`n−1`以下の整数を`a`と置き、`n`がその整数aで割りきれなかったら`False`を返す関数を作成しました。）

どのようにプログラムすればいいのでしょうか。ご回答よろしくお願いします。


CC BY-SA 4.0
2020-09-13T11:20:28.533
70350
2020-09-15T08:56:36.943
2020-09-15T08:56:36.943
29826
41837
question
haskell
Haskellの素数判定でコンパイルエラー


> Parse error: naked expression at top level

これは式がトップレベルにあることがおかしいというエラーです。171行目にそのエラーがあるというメッセージですがおそらく質問者は
_sample1002.hs_ にコードを足していっていると予想すると次の行でしょう。

[code]

    a>=2　&& a<=n−１
    
[/code]

またこの行には他にも問題があります。全角空白と全角の`１`が含まれています。これらは半角でないといけません。

さて、

> `n` を `2` から `n−1` まで割っていったときに、割り切れない

なるべくこのアルゴリズムに沿うようにプログラムしたのが下記のソースコードです。

[code]

    prime :: Int -> Bool
    prime 1 = False -- (1)
    prime 2 = True -- (2)
    prime n = all ((/= 0) . (n `mod`)) [2 .. n - 1] -- (3)
    
[/code]

まず、引用したアルゴリズムだと `1` のときと `2` のときの判定ができないのでそのときは `True` であると定義します（(1)・(2)）。

(3)
のその他の場合ですが、[`all`](https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:all)
関数を使います。これは下記のような型となっていて第1引数の関数を第2引数のリストの要素に適用しその結果が全て `True` である場合に `True`
を返します（型は簡単のため具体化しています）。

[code]

    all :: (a -> Bool) -> [a] -> Bool
    
[/code]

`n` が `5` の場合を考えて順に追ってみましょう。まず (3) の部分式である下記に注目します。

[code]

    [2 .. n - 1]
    
[/code]

これは `n` が `5` のとき下記となります。

[code]

    [2 .. 4]
    
[/code]

このリストの要素に `all` の第1引数を適用します。すると下記となります。

[code]

    [((/= 0) . (n `mod`)) 2, ((/= 0) . (n `mod`)) 3, ((/= 0) . (n `mod`)) 4]
    
[/code]

これは `n` が `5` なので

[code]

    [((/= 0) . (5 `mod`)) 2, ((/= 0) . (5 `mod`)) 3, ((/= 0) . (5 `mod`)) 4]
    
[/code]

ここで、次の2つの式は同じ意味です。

[code]

    ((/= 0) . (5 `mod`)) 2
    (5 `mod` 2) /= 0
    
[/code]

よって

[code]

    [(5 `mod` 2) /= 0, (5 `mod` 3) /= 0, (5 `mod` 4) /= 0]
    
[/code]

となります。これを計算すると

[code]

    [1 /= 0, 2 /= 0, 1 /= 0]
    
[/code]

となり、さらに

[code]

    [True, True, True]
    
[/code]

となります。要素が全部 `True` なので (3) の `=` の右辺は全体で `True` となります。`n` が `5`
の場合これは素数なので合っています。

一点注意として、実際のプログラムはこの順番で計算しているわけではありません。しかし、結果は同じになります。


CC BY-SA 4.0
2020-09-13T14:06:57.367
70356
2020-09-13T14:16:01.043
2020-09-13T14:16:01.043
153
153
70350
answer