bash - 埃拉托色尼筛法 UNIX 脚本

Question

我正在编写一个 UNIX 脚本来使用筛子生成素数。我一直在第 19 行得到一个糟糕的模除法，我似乎无法弄清楚为什么。

我尝试了各种不同的格式，不知道正确的方法是什么。

#!bin/bash
read -p "Upper limit? :" answer
theMultiple=2

#populate the array
for ((i=2;i<$answer;i++)); do
   sieveArray[$i]=$i
done
#Use Sieve
for ((i=0;i<=${#sieveArray[*]}; i++)); do
   if [ $[$(($[${sieveArray[$i]}] % $theMultiple))] -eq 0 ]; then
         theMultiple=${sieveArray[$i]}
         echo $theMultiple
         for ((j=$i;j<${#sieveArray[*]};j++)); do
            if [ $[$(($[${sieveArray[$j]}] % $theMultiple))] -eq 0 ]; then
               sieveArray[$j]=0
            fi
         done
   fi
done
}

Answer 1

您开始在索引 2 处填充 sieveArray，但在主循环中，您开始在索引 0 处使用它。默认情况下，前两个元素可能设置为零，这会导致除以零。

Answer 2

你可以用更少的 bash 算法和更多的命令来写不同的代码：

#!/bin/bash
limit=$1
sieve="$(seq 2 $limit|sort)"

for n in 2 $(seq 3 2 $limit)
do
  sieve="$(comm -23 <(echo "$sieve") <(seq $(($n * $n)) $n $limit|sort))"
done

echo "$sieve"|sort -n

seq用于生成数字和倍数的列表。 comm用于从sieve变量中删除倍数。正如comm预期的按字母顺序排序的数据（10 在 9 之前），每次都必须对数字列表进行排序。

该for循环经过轻微优化，不包括偶数，除了 2。