スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

原始根を求めるHaskellプログラムの例

奇素数を法とする原始根を求める Haskell プログラムの例。

プログラム例

main = printElems 14 $ listPrimitiveRoots $ sieve $ filter odd [3..]

-- リストの各要素を表示
printElems :: Show a => Int -> [a] -> IO()
printElems n xs = mapM_ print $ take n $ xs

-- 素数 p と、p を法とする原始根との組
listPrimitiveRoots :: [Integer] -> [(Integer, [Integer])]
listPrimitiveRoots primes = [ (p, primitiveRoots p) | p <- primes ]

-- 与えられた素数を法とする原始根を求める
primitiveRoots :: Integer -> [Integer]
primitiveRoots p = filter (isPrimitive 1 0) [2 .. p-1]
  where
    -- x^i mod p /= 1 (i=1,...,p-2) かどうか
    isPrimitive :: Integer -> Integer -> Integer -> Bool
    isPrimitive a i x 
      | i >= p - 1 = True
      | i == 0     = isPrimitive x 1 x
      | otherwise  = a `mod` p /= 1 && 
                     isPrimitive (a * x) (i + 1) x

-- 素数リスト (エラトステネスの篩)
sieve :: [Integer] -> [Integer]
sieve (p : xs) = p : sieve [ n | n <- xs, n `mod` p /= 0 ]

実行結果:

(3,[2])
(5,[2,3])
(7,[3,5])
(11,[2,6,7,8])
(13,[2,6,7,11])
(17,[3,5,6,7,10,11,12,14])
(19,[2,3,10,13,14,15])
(23,[5,7,10,11,14,15,17,19,20,21])
(29,[2,3,8,10,11,14,15,18,19,21,26,27])
(31,[3,11,12,13,17,21,22,24])
(37,[2,5,13,15,17,18,19,20,22,24,32,35])
(41,[6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35])
(43,[3,5,12,18,19,20,26,28,29,30,33,34])
(47,[5,10,11,13,15,19,20,22,23,26,29,30,31,33,35,38,39,40,41,43,44,45])

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。