Sieve of Eratosthenes UNIX Script

Question

I'm writing a UNIX script to use the sieve to generate prime numbers. I keep getting a bad modulo division on line 19, and I can't seem to figure out why.

I have tried all kinds of different formatting, not sure what the right way is.

#!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

The code you have provided has multiple issues and the core cause of the error you run into is the erroneous logic used in the code. In your confusion you fail to track the flow of the code to see when and why the variable theMultiple is set to zero leading to the error in the modulo operation.

NOTICE that the code you have provided is generally designed to use brute force and therefore the question title Sieve of Eratosthenes UNIX Script is misleading, because there is no sieving by marking of multiples of already found primes implemented in the code.

The code you have provided does not run at all because of multiple syntax error issues as for example: line 15: 0 % : syntax error: operand expected (error token is "% ") or superfluous } in the last line.

This all said a working code nearest to the intended one running in bash version 5.1.16 is as follows:

#!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

The answer provided by Mickaël Bucas is still using a brute force even if in a optimized way refraining from explicit usage of loops in favor of delegating the marking of multiples to the comm command which depends on preceding call to sort.

The actual sieving algorithm is used in following bash code which implements the fact that in bash it is not necessary to create all array elements before setting values to them. In bash any name at any index has already a value being an empty string with which bash responds on request:

#!/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

By the way: this question and its up to now answers is probably one of the reasons why AIs like ChatGPT fail sometimes to provide correct answers because of relying on the fact that the answers to such an old question must be correct, else it would be another, better and accepted answer there.