bash - 如何使这个 bash 素数生成器更快 [SPOJ]

Question

我正在做名为 Prime Generator 的 SPOJ 挑战，但是在 BASH 中，法官说

time limit exceeded

代码给出了请求的结果，并且这个算法在 C++ 和 Java 中被接受

#!/bin/bash

read ITERATIONS

for (( i=0; i<$ITERATIONS; i++ ))
do
        read START END

        for (( j=$START; j<=$END; j++ ))
        do
                isPrime=1

                if [ $j -eq 1 ]
                then
                        isPrime=0
                fi

                for (( k=2; k*k<=$j; k++ ))
                do
                        if (($j % $k == 0))
                        then
                                isPrime=0
                                break
                        fi
                done

                if [ $isPrime -eq 1 ]
                then
                        echo "$j"
                fi
        done
done

我的问题是，我怎样才能加快这段代码的速度？我是不是做了什么傻事导致它变慢了？

Answer 1

使用 bc 是一个选项吗？

read -r ITERATIONS
for ((i = $ITERATIONS; i; --i)); do
        read -r START END
        ((START = START == 1 ? 2 : START))
        echo '
for (j='"$START"'; j<='"$END"'; ++j) {
        isprime=1
        for (k=2; k*k<=j; ++k) {
                if (j%k == 0) {
                        isprime=0
                        break
                }
        }
        if (isprime == 1) {
                j
        }
}
        ' | bc
done

或者可能会增加一些并发性，但我们需要同步输出:

tmps=()
read -r ITERATIONS
for ((i = $ITERATIONS; i; --i)); do
        read -r START END
        ((START = START == 1 ? 2 : START))
        tmp=$(mktemp)
        tmps+=($tmp)
        (
        echo '
for (j='"$START"'; j<='"$END"'; ++j) {
        isprime=1
        for (k=2; k*k<=j; ++k) {
                if (j%k == 0) {
                        isprime=0
                        break
                }
        }
        if (isprime == 1) {
                j
        }
}
        ' | bc
        ) > "$tmp" &
done
wait
cat "${tmps[@]}"
rm "${tmps[@]}"