今日も楽しく競技brainfuck。

A - 素数判定

「素数っぽい」かどうかを判定する問題。 $1$は「素数っぽ」くなくて、$2, 3, 5$は「素数っぽい」。 それ以外の数に関して、$2, 3, 5$のいずれでも割れなければ「素数っぽい」。

10進最下位桁と10進各桁の総和しか使わないので簡単、なはずが予想より手間取ってしまった。

>>>>>>>>>>>>>>>>

p 0 0 0 0 nl 0 0 0 _ _ _ _ n1 0 0 0 n0 0 0 0
p is 1 then Not Prime
p is 2 then Prime

input
,----------[>>>>,----------]
<<<<[>++++++[<------>-]<- <<<<]
>>>> [>>>>] <<<<

is 1
<<<<[>+>+<<-] >[<+>-]>[>>>+<<<[-]]>>>- n2 0 0 0 n1 0 0 0 n0 *is_n_=_n0*
[[-]< *n0*
    [>+>+<<-] >[<+>-] >-- n0 0 *is_not_1*
    [<->[-]] <+ n0 *is_1*
    [ < <<<< <+> >>>> > -] put not prime flag
    <
>]< *n0* 0 0 0

[<<<<] <[>+>+<<-]>[<+>-]+>[<->[-]]<[- >>>> [>>>>] <<<< begin
is 2 or 3 or 5
<<<<[>+>+<<-] >[<+>-]>[>>>+<<<[-]]>>>- n2 0 0 0 n1 0 0 0 n0 *is_n_=_n0*
[[-]< *n0*
    [>+>>+>>+>+<<<<<<-] >[<+>-] n *0* 0 n 0 n n
    >>--->>---->------ n 0 0 n_2 0 n_3 *n_5*
    [<
        [<+<
            [<+<
                +
            >>-]
            <[>+<-]>
        >>-]
        <[>+<-]>
    >-] n product 0 n_2 0 n_3 *0*
    <[-]<<[-]<< n *product*
    [>-<[-]]>+ n 0 *is_2_3_or_5*
    [- << <<<< <++> >>>> >>] put prime flag
    << *n*
>]< *n0* 0 0 0
[<<<<] ] >>>> [>>>>] <<<< end

[<<<<] <[>+>+<<-]>[<+>-]+>[<->[-]]<[- >>>> [>>>>] <<<< begin
is 2n or 5n
case 1
n0 is 0 or 2 or 4
[>+>>+>>+>+<<<<<<-] >[<+>-] n *0* 0 n 0 n n
>>->>--->----- n 0 0 n_0 0 n_2 *n_4*
[<
    [<+<
        [<+<
            +
        >>-]
        <[>+<-]>
    >>-]
    <[>+<-]>
>-] n product 0 n_0 0 n_2 *0*
<[-]<<[-]<< n *product*
[>-<[-]]>+ n 0 *is_0_2_or_4*
[- << [<<<<] <+> >>>> [>>>>] <<] put not prime flag
<< *n*
[<<<<] ] >>>> [>>>>] <<<< end

[<<<<] <[>+>+<<-]>[<+>-]+>[<->[-]]<[- >>>> [>>>>] <<<< begin
is 2n or 5n
case 2  split to avoid TLE
n0 is 5 or 6 or 8
[>+>>+>>+>+<<<<<<-] >[<+>-] n *0* 0 n 0 n n
>>------>>------->--------- n 0 0 n_5 0 n_6 *n_8*
[<
    [<+<
        [<+<
            +
        >>-]
        <[>+<-]>
    >>-]
    <[>+<-]>
>-] n product 0 n_5 0 n_6 *0*
<[-]<<[-]<< n *product*
[>-<[-]]>+ n 0 *is_5_6_or_8*
[- << [<<<<] <+> >>>> [>>>>] <<] put not prime flag
<< *n*
[<<<<] ] >>>> [>>>>] <<<< end

[<<<<] <[>+>+<<-]>[<+>-]+>[<->[-]]<[- >>>> [>>>>] <<<< begin
is 3n
<<<< [>>>> -[<<<<+>>>>-] <<<< <<<<] >>>> - p 0 0 0 0 *sum*
>+++< *sum* 3
[>- [>+>+<<-] >[<+>-] >[<->[-]] <+ [<+++>-] <<-] *0* sum_mod_3
>--- [<->[-]] <+ *is_3n*
[<<<< <+> >>>>-] 1 0 0 0 0 *0*
+
[<<<<] ] >>>> [>>>>] <<<< end

[[-] <<<<] < *p* 0 0 0 0 0 0 0 0 _ _ _ _ where p is 0 1 or 2
[>+>+<<-] >[<->[-]] <+[>>++<<-] >> *p* where p is 1 or 2

-- *is_not_prime*
[[-]
        print N o t ' '
        ++++++[>+++++++++++++<-]>.< 78
        ++++[>++++++++<-]>+.< 111
        >+++++.< 116
        +++++++[>------------<-]>.< 32
        >[-]<<
]
print P r i m e
++++++++[>++++++++++<-]>.< 80
+++++[>+++++++<-]>-.< 114
>---------.< 105
>++++.< 109
>--------.< 101
++++++++++. 10
  • 各桁の間を空けたの必要なかった。
  • $(n - x)(n - y) = 0 {\rm iff} x = 0 {\rm or} y = 0$ってのを使って楽しようとしたのに、掛け算をまとめてやると遅いので分割するなどしている。素直に比較すれば良かったのでは。
  • nestさせてまとめて掛け算すると遅い。例えば$-1 \times -1 \times -1 \times -1$は$255^4$回以上加算が行われる。複数回に分けて演算すべき。
  • 出力確定のflagを持っておいてそれが$0$のときだけ処理を走らせる形式は、まあ普通ではあるけど便利だなあと思った。

WA生やしたときにそもそもの解法が間違ってないことを確認するために書いたpythonのコードもついでに載せておく。なおそのWAは、$(n-5)(n-6)(n-8)$を計算するところを、-をひとつ忘れて$(n-4)(n-6)(n-8)$にしていたのが原因だった。

#!/usr/bin/env python3
n = int(input())
def is_prime_like(n):
    if n == 1:
        return False
    if n in [2, 3, 5]:
        return True
    if int(list(str(n)).pop()) in [0, 2, 4, 5, 6, 8]:
        return False
    if sum(map(int,list(str(n)))) % 3 == 0:
        return False
    return True
if not is_prime_like(n):
    print('Not ', end='')
print('Prime')
  • Tue Sep 22 00:54:24 JST 2015
    • コードの反省を追記