wktk's blog

Pxem で素数判定をする

ag.- (= 6) が素数かどうか

ag.-.tab.-.c.w.c.c.!.m.x.strue.paa.-.c.c.a.c.wab.-.+.c.m.%.cab.-.y.s.sfalse.paa.-ab.-aa.-.aaa.-.a.a.pxe
=> false

dd.! (= 10,000) が素数かどうか

dd.!.tab.-.c.w.c.c.!.m.x.strue.paa.-.c.c.a.c.wab.-.+.c.m.%.cab.-.y.s.sfalse.paa.-ab.-aa.-.aaa.-.a.a.pxe
=> false

dd.!ah.-.+ (= 10,007) が素数かどうか

dd.!ah.-.+.tab.-c.w.c.c.!.m.x.strue.paa.-.c.c.a.c.wab.-.+.c.m.%.cab.-.y.s.sfalse.paa.-ab.-aa.-.aaa.-.a.a.pxe
=> true

今回の方針は、

  • 2 から順に数え上げながら割っていく
  • 途中で割り切れたら素数でない (false)
  • 引数の平方根を超える数までカウントアップできたら素数 (true)

です

素数でない場合に、引数を割り切れる最小の数をドヤ顔で表示することもできます
dd.!ab.-.+ (= 10,001) の場合

dd.!ab.-.+.tab.-.c.w.c.c.!.m.x.strue.paa.-.c.c.a.c.wab.-.+.c.m.%.cab.-.y.s.tfalse(.p.m.n).paa.-ab.-aa.-.aaa.-.a.a.pxe
=> false(73)

もちろんファイルサイズは 0 バイトです
ただこれだと数え上げる途中に合成数でも割ってしまっているので、改善の余地があるかも…?

Author

@wk

Tags