埃拉托色尼筛法 UNIX 脚本

问题描述 投票:0回答:3

我正在编写一个 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
}
bash unix
3个回答
1
投票

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


0
投票

您可以使用更少的 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 之外的偶数。


0
投票

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

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 这样的人工智能有时无法提供正确答案的原因之一,因为这样一个老问题的答案必须是正确的,否则它会是另一个更好的、被接受的答案。

© www.soinside.com 2019 - 2024. All rights reserved.