他人のHaskell日記 RSSフィード

Haskell初心者が、リハビリがてらに「ふつける」と「入門Haskell」片手に、試行錯誤するサイト。

2006-06-17

素数狩り 擬素数狩り - 他人のHaskell日記 を含むブックマーク

素数のフリしてお高くとまっている偽素数どもを発見し晒し上げる

正しい素数列としてid:nobsunのエラトステネスのふるいを

(http://haskell.g.hatena.ne.jp/nobsun/20060617)

フェルマーテストとしてd:id:nurseの書いたものをhaskellに書き換えたものを使います。

(http://d.hatena.ne.jp/nurse/20060616)

import List

--エラトステネスのふるい(id:nobsun)
sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]
primes = sieve [2..]

--フェルマーテスト(id:nurse)のHaskell版
primes' = 2:filter(\x -> ((2^(x-1)) `mod` x) == 1)[3..]

--ミラーテスト(id:taninsw)
primes'' = 2:filter millerTest [3..] 
millerTest = check.map head.group.modList where
  check (1:[]) =  True
  check (1:(-1):_) = True
  check _ = False
  modList n = map (g.(`mod` n).(2^)) (f (n-1)) where
    f x | even x = x:f (x`div`2)
        | otherwise = x:[]
    g s | s > 1 = s - n 
        | otherwise = s

--テスト用コード

--それぞれの素数列のn番目の要素を抜き出す
(!!!) n =  map ($ n)  [(primes !!),(primes' !!),(primes'' !!)]

--「正しい素数列」と「擬素数を含む素数列」から「(素数の振りをした)擬素数の配列」を作る
unmatch x@(xh:xt) y@(yh:yt) 
  | xh >  yh = yh:unmatch x yt  
  | xh <  yh = xh:unmatch xt y  
  | xh == yh = unmatch xt yt

実行結果

*Main> take 10 $ unmatch primes primes'                       --擬素数(最初の10個)
[341,561,645,1105,1387,1729,1905,2047,2465,2701]
*Main> take 10 $ unmatch primes primes''                      --強擬素数(最初の10個)
[2047,3277,4033,4681,8321,15841,29341,42799,49141,52633]

*Main> takeWhile (<10000) $ unmatch primes primes'            --擬素数(10000以下)
Loading package haskell98-1.0 ... linking ... done.
[341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,4371,4681,5461,6601,7957,8321,8481,8911]
*Main> takeWhile (<10000) $ unmatch primes primes''           --強擬素数(10000以下)
[2047,3277,4033,4681,8321]

ミラーテストで現れる擬素数は、フェルマーテストでも擬素数になっています。

逆にいえば、フェルマーテストを通過できなかったものは、ミラーテストも通過できない、ということです。

ちなみに、フェルマーテストミラーテストも中身はまったく理解していません。

DavianDavian2012/01/06 16:14God help me, I put aside a whole afternoon to fuigre this out.

udveweudvewe2012/01/06 19:2621ObXs <a href="http://szbmaiurkppr.com/">szbmaiurkppr</a>

pjpdsaocpjpdsaoc2012/01/07 22:36jPUNSS , [url=http://dwepjvfdsppz.com/]dwepjvfdsppz[/url], [link=http://ckcdiyjoding.com/]ckcdiyjoding[/link], http://oxjlddkdkqxu.com/

ywxbdkqywxbdkq2012/01/09 23:22fRxEP3 <a href="http://fyiftgcnicxn.com/">fyiftgcnicxn</a>

qpjdaenmqpjdaenm2012/01/11 03:44hHRgBW , [url=http://yrdxnqbyzdzz.com/]yrdxnqbyzdzz[/url], [link=http://tulnkdnbqovm.com/]tulnkdnbqovm[/link], http://djxnfmrqmwqd.com/

HedHed2013/07/27 04:52Weeeee, what a quick and easy sotnilou.

OmarOmar2013/07/30 01:33Wow, this is in every recpset what I needed to know.

MikiMiki2013/08/02 22:23This was so helpful and easy! Do you have any artielcs on rehab? http://mtlhgz.com [url=http://hsyjlrwhamf.com]hsyjlrwhamf[/url] [link=http://zskglfaz.com]zskglfaz[/link]

DennisRourbDennisRourb2017/03/28 07:50metronidazol creme bijsluiter
<a href= http://jadalipfor.e-monsite.com >metronidazol hond bijsluiter</a>
<a href=http://lonsibounm.eklablog.net>propranolol</a>
strattera add inattentive
<a href= http://bisacodyl.tilda.ws/bisacodylhtml >bisacodyl 5 mg zetpil</a>
<a href=http://brandimroz.bloggsite.se>flagyl ovules kopen</a>
flagyl 500 mg bg

WilliamGlushWilliamGlush2017/03/30 08:33cipralex 10 mg nebenwirkungen
<a href= http://nouw.com/rematague >gabapentin 300 und alkohol</a>
<a href=http://nouw.com/rematague>gabapentin micro labs 400mg</a>
azithromycin 500 hec
<a href= https://agnusdinap.yolasite.com >nifurantin und pille</a>
<a href=http://lonnielenn.edublogs.org/2017/03/27/azithromycin/>azithromycin 500 1a pharma in der schwangerschaft</a>
gabapentin teva

EdwardBidgeEdwardBidge2017/03/30 09:10flagyl 400 metronidazole
<a href= http://antionehoy.e-monsite.com >dalacin c penicillin allergy</a>
<a href=http://kathyrnkes.blogg.no>ibux barn dosering</a>
pergotime 50 mg pris
<a href= http://devinnair.startbewijs.nl >proscar finasteride msd</a>
<a href=http://lincolnmaw.ek.la>doxylin mot lungebetennelse</a>
ibux barn 10 år

SamuelRexSamuelRex2017/04/01 09:08ibux gel barn
<a href= http://delmydavid.blogg.se >ibux 400 mg dose</a>
<a href=http://emmanuelje.tribalpages.com>proscar (finasteride) and avodart (dutasteride)</a>
pergotime bivirkninger
<a href= http://ellsworthut.page4.me >dalacin</a>
<a href=http://trinidadpi.bloggsite.se>zovirax 5 cream for genital herpes</a>
proscar apoteket

ReubencoarpReubencoarp2017/04/01 14:03comprar qlaira preço
<a href= http://www.onweb.fr?company_id=17318 >qlaira engorda muito</a>
<a href=http://jonsuchars.oneminutesite.it>ciprofloxacino posologia para que serve</a>
ciprofloxacino colirio preço
<a href= http://andreahatt.wifeo.com >excedrin pm ingredients</a>
<a href=http://janethorua.guildomatic.com>augmentin</a>
ciprofloxacino preço nissei

WilliamdenWilliamden2017/04/03 09:12qlaira bula efeitos colaterais
<a href= http://jorgemanwa.jimdo.com >diclofenaco pomada preço</a>
<a href=http://lauriceeag.freeblog.site>ciprofloxacino hidrocortisona otologico</a>
nexium 20 mg preço ultrafarma
<a href= http://lauriceeag.freeblog.site >ciprofloxacino preço drogasil</a>
<a href=http://chucklyshe.edublogs.org/2017/04/02/nexium/>remedio nexium 20 mg preço</a>
nexium 20 mg bula pdf

MichaeldowMichaeldow2017/04/06 07:34finasteride 1 mg precio
<a href= http://elwoodeast.soup.io >nolvadex 20 mg effets secondaires</a>
<a href=http://project200559.tilda.ws>amoxicilline acide clavulanique grippe</a>
avis clomid duphaston
<a href= http://leroypusey.startspot.nl >tolexine 50 prix</a>
<a href=http://earledelli.e-monsite.com/pages/clomid.html>clomid et ovitrelle opk</a>
amoxicilline 250 mg posologie

MatthewfubMatthewfub2017/04/06 09:51dapoxetine 30 mg price in india
<a href= http://salomemahe.page4.me >prix finasteride 1mg</a>
<a href=http://jolenemale.onlc.be>nolvadex dosage</a>
nolvadex 20 mg effets secondaires
<a href= http://salomemahe.page4.me >finasteride 5mg prix</a>
<a href=http://margorieza.spruz.com>doxyval 100 prix</a>
doxyval chien prix

RichardQuavaRichardQuava2017/04/10 09:36etoricoxib torrinomedica
<a href= http://cruzliedy.guildomatic.com >bijsluiter celecoxib sandoz</a>
<a href=http://markettaro-blog.logdown.com>amoxicillina sciroppo torrino</a>
amoxicillina sciroppo torrino
<a href= http://elishakoew.ayosport.com/article-15572-zovirax >zovirax pomata per herpes zoster</a>
<a href=http://jinnychoin.familybelle.com>janumet 50/1000 mg</a>
janumet 50 mg/500