#!/bin/sh
#
#
# Author:      Kai Visch-Sluyter
#              Universitaet Osnabrueck
#              Mon Jun  2 12:06:11 MET DST 1997
# File:        Prim
# Description: Prim ObereSchranke
#		Gibt alle Primzahlen bis ObereSchranke aus.
#		Nach dem Sieb des Eratosthenes.
#

PATH=:/usr/local/gnu/bin:

# Fehlerbehandlung
#
if [ $# != 1 ]
then
	echo "Usage: Prim UpperBound" 1>&2
	exit 1
fi

i=`expr length "$1"`

if [ $i -eq 0 ]
then
	echo "Hey: Don't try such things" 1>&2
	exit 1
fi

if [ `expr "$1" : '[0-9]*'` -lt $i ]
then
	echo "Error: UpperBound must be non-negative Integer" 1>&2
	exit 1
fi

if [ $i -gt 5 ]
then
	echo "Sorry: Can't handle such big numbers" 1>&2
	exit 1
fi

if [ $1 -gt 65536 ]
then
	echo "Sorry: Can't handle such big numbers" 1>&2
	exit 1
fi
#
# Ende Fehlerbehandlung


os=$1	# obere Schranke
		
bv=0	# Bitvektor: 0=Primzahl (Voreinstellung) 1=keine Primzahl (sicher)
	# fuer die Zahlen {3,5,7,...}

# Bitvektor mit Nullen initialisieren:
#
i=2
while [ $i -lt $os ]
do
	bv=$bv$bv
	i=`expr $i \* 2`
done

# Wurzel der oberen Schranke berechnen
#
wos=2
while [ `expr $wos \* $wos` -lt $os ]
do
	wos=`expr $wos \* 2`
done

# 2 ausgeben, falls obere Schranke entsprechend gross.
#
if [ $os -ge 2 ]
then
	echo -n "2 "
fi

# Fuer alle ungeraden Zahlen zwischen 3 und der Wurzel von obere Schranke wird
# jeweils die kleinste Primzahl ermittelt, ausgegeben, ihre Vielfachen als 
# "nicht Primzahlen" markiert, und alle Zahlen kleiner/gleich dieser Primzahl
# aus dem Bitvektor geloescht
#
i=3
p='.'	# idiotische Suchmaske wegen Memory Fault in Prim5	
while [ $i -le $wos ]
do
	echo -n "$i "
	bv=`echo $bv | sed 's/^1*0//' | sed 's/\('$p$p'\)./\11/g'`
	pos=`expr index $bv [0]`
	i=`expr $i + \( $pos \* 2 \)`
	j=1
	while [ $j -le $pos ]
	do
		p=$p'.'
		j=`expr $j + 1`
	done
done	

bv=$bv"0"	# Sicherheit

# Fuer alle ungeraden Zahlen zwischen der Wurzel von obere Schranke und
# der oberen Schranke wird jeweils die kleinste Primzahl ermittelt,
# ausgegeben, und alle Zahlen kleiner/gleich dieser Primzahl aus dem
# Bitvektor geloescht
#
while [ $i -le $os ]
do
	echo -n "$i "
	bv=`echo $bv | sed 's/^1*0//'`
	pos=`expr index $bv [0]`
	i=`expr $i + \( $pos \* 2 \)`
done

echo

exit 0