#!/bin/bash
# sieve.sh

# ¿¡¶óÅ佺Å׳׽ºÀÇ Ã¼(Sieve of Erastosthenes)
# ¼Ò¼ö¸¦ ã¾ÆÁÖ´Â °í´ëÀÇ ¾Ë°í¸®Áò.

# ÀÌ ½ºÅ©¸³Æ®´Â ¶È°°Àº C ÇÁ·Î±×·¥º¸´Ù µÎ ¼¼¹è´Â ´õ ´À¸®°Ô µ¿ÀÛÇÕ´Ï´Ù.

LOWER_LIMIT=1       # 1 ºÎÅÍ.
UPPER_LIMIT=1000    # 1000 ±îÁö.
# (½Ã°£ÀÌ ÁÖü¸øÇÒ Á¤µµ·Î ³²¾Æ µ·´Ù¸é ÀÌ °ªÀ» ´õ ³ô°Ô Àâ¾Æµµ µË´Ï´Ù.)

PRIME=1
NON_PRIME=0

let SPLIT=UPPER_LIMIT/2
# ÃÖÀûÈ­:
# ¿ÀÁ÷ »óÇÑ°ªÀÇ ¹Ý¸¸ È®ÀÎÇØ º¸·Á°í ÇÒ °æ¿ì ÇÊ¿ä.


declare -a Primes
# Primes[] ´Â ¹è¿­.


initialize ()
{
# ¹è¿­ ÃʱâÈ­.

i=$LOWER_LIMIT
until [ "$i" -gt "$UPPER_LIMIT" ]
do
  Primes[i]=$PRIME
  let "i += 1"
done
# ¹«ÁË°¡ ¹àÇôÁö±â Àü±îÁö´Â ¹è¿­ÀÇ ¸ðµç °ªÀ» À¯ÁË(¼Ò¼ö)¶ó°í °¡Á¤.
}

print_primes ()
{
# Primes[] ¸â¹öÁß ¼Ò¼ö¶ó°í ¹àÇôÁø °ÍµéÀ» º¸¿©ÁÝ´Ï´Ù.

i=$LOWER_LIMIT

until [ "$i" -gt "$UPPER_LIMIT" ]
do

  if [ "${Primes[i]}" -eq "$PRIME" ]
  then
    printf "%8d" $i
    # ¼ýÀÚ´ç 8 Ä­À» Á༭ ¿¹»Ú°Ô º¸¿©ÁÝ´Ï´Ù.
  fi
  
  let "i += 1"
  
done

}

sift () # ¼Ò¼ö°¡ ¾Æ´Ñ ¼ö¸¦ °É·¯³À´Ï´Ù.
{

let i=$LOWER_LIMIT+1
# 1 ÀÌ ¼Ò¼öÀÎ °ÍÀº ¾Ë°í ÀÖÀ¸´Ï, 2 ºÎÅÍ ½ÃÀÛÇÕ´Ï´Ù.

until [ "$i" -gt "$UPPER_LIMIT" ]
do

if [ "${Primes[i]}" -eq "$PRIME" ]
# ÀÌ¹Ì °É·¯Áø ¼ýÀÚ(¼Ò¼ö°¡ ¾Æ´Ñ ¼ö)´Â °Ç³Ê¶Ý´Ï´Ù.
then

  t=$i

  while [ "$t" -le "$UPPER_LIMIT" ]
  do
    let "t += $i "
    Primes[t]=$NON_PRIME
    # ¸ðµç ¹è¼ö´Â ¼Ò¼ö°¡ ¾Æ´Ï¶ó°í Ç¥½ÃÇÕ´Ï´Ù.
  done

fi  

  let "i += 1"
done  


}


# ÇÔ¼öµéÀ» ¼ø¼­´ë·Î ºÎ¸¨´Ï´Ù.
initialize
sift
print_primes
# ÀÌ·±°ÍÀ» ¹Ù·Î ±¸Á¶Àû ÇÁ·Î±×·¡¹ÖÀ̶ó°í ÇÑ´ä´Ï´Ù.

echo

exit 0



# ----------------------------------------------- #
# ´ÙÀ½ ÄÚµå´Â ½ÇÇàµÇÁö ¾Ê½À´Ï´Ù.

# ÀÌ°ÍÀº Stephane Chazelas ÀÇ Çâ»óµÈ ¹öÀüÀ¸·Î ½ÇÇà ¼Óµµ°¡ Á» ´õ ºü¸¨´Ï´Ù.

# ¼Ò¼öÀÇ ÃÖ´ë ÇѰ踦 ¸í·É¾îÁÙ¿¡¼­ ÁöÁ¤ÇØ ÁÖ¾î¾ß µË´Ï´Ù.

UPPER_LIMIT=$1                  # ¸í·É¾îÁÙ¿¡¼­ÀÇ ÀÔ·Â.
let SPLIT=UPPER_LIMIT/2         # ÃÖ´ë¼öÀÇ Áß°£.

Primes=( '' $(seq $UPPER_LIMIT) )

i=1
until (( ( i += 1 ) > SPLIT ))  # Áß°£±îÁö¸¸ È®ÀÎ ÇÊ¿ä.
do
  if [[ -n $Primes[i] ]]
  then
    t=$i
    until (( ( t += i ) > UPPER_LIMIT ))
    do
      Primes[t]=
    done
  fi  
done  
echo ${Primes[*]}

exit 0