埃拉托色尼筛法 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 之外的偶数。

Answer 3

您提供的代码存在多个问题，导致您遇到错误的核心原因是代码中使用的错误逻辑。在您的困惑中，您无法跟踪代码流程以查看变量

theMultiple

何时以及为何设置为零，从而导致模运算中出现错误。

注意，您提供的代码通常设计为使用暴力破解，因此问题标题Eratosthenes UNIX Script 的筛分具有误导性，因为代码中没有通过标记已找到的素数的倍数来进行筛选。

您提供的代码由于多个语法错误问题而根本无法运行，例如：

line 15: 0 % : syntax error: operand expected (error token is "% ")

或者最后一行中多余的

}

。

这一切都表明，最接近 bash 版本 5.1.16 中运行的预期代码的工作代码如下：

#!bin/bash
answer=100 # ; read -p "Upper limit? :" answer
theMultiple=2
#populate the array
for (( i=1 ; i<=$answer; i++ )); do
   sieveArray[$i]=$i  #; echo ${sieveArray[$i]}
done
#Use Sieve
for ((i=2 ; i<=${#sieveArray[@]} ; i++ )); do
   if [ ${sieveArray[i]} -gt 0 ]; then
         theMultiple=${sieveArray[$i]}
         echo -n "  $theMultiple"
         for ((j=i ; j<=${#sieveArray[@]} ; j++)); do
            if [ $(( sieveArray[j] % theMultiple)) -eq 0 ]; then
               sieveArray[j]=0
            fi
         done
   fi
done

Mickaël Bucas提供的答案仍然使用蛮力，即使以优化的方式避免显式使用循环，而是将倍数标记委托给comm

命令，该命令取决于之前对

sort

的调用.

实际的筛选算法用于以下 bash 代码中，该代码实现了这样一个事实：在 bash 中，无需在为其设置值之前创建所有数组元素。在 bash 中，任何索引处的任何名称都已经有一个值，该值是 bash 根据请求响应的空字符串：

#!/usr/bin/bash
#   default n=100
if [[ n -eq "" ]]; then n=$1; fi
if [[ n -eq "" ]]; then n=100; fi
if [[ n -lt 2 ]]; then exit; else echo -n "  2"; fi ; if [[ n -eq 2 ]]; then exit; fi   
for ((i=3; i<=n ; i=i+2 )); do
    if [[ $(( i*i )) -gt n ]]; then break; fi
    if [[ isMultiple[$i] -eq 1 ]]; then continue; fi 
    for ((k=$(( i*i )) ; k<=n ; k=k+i)); do
        isMultiple[$k]=1
    done
done
for (( i=3; i<=n ; i=i+2 )); do  
    if [[ isMultiple[i] -eq "" ]]; then  echo -n "  $i"; fi  
done
echo

顺便说一句：这个问题及其迄今为止的答案可能是像 ChatGPT 这样的人工智能有时无法提供正确答案的原因之一，因为这样一个老问题的答案必须是正确的，否则它会是另一个更好的、被接受的答案。