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