Bash Collective #7
Ontbinden in factoren

De opdracht

Schrijf een programma wat een getal ontbindt in factoren en laat zien of het een priemgetal is

De makkelijkste oplossing is natuurlijk gebruik van ‘factor’, maar helaas laat dat programma nog niet zien of het getal priem is:

$ factor 30
30: 2 3 5

Team 1

Dit script toont alle getallen waardoor gedeeld kan worden, dus helaas ook getallen die zelf weer ontbonden kunnen worden.

#!/bin/bash
number=$1
prime=true
for i in $(seq 2 1 $(($number - 1)))
do
  if [ $(($number % $i)) -eq 0 ]
  then
     prime=false
     out="$out \n number $i a factor"
  fi
done
if [ "$prime" = true ]
  then
  echo "Optimus Prime!"
fi

echo -e $out

Team 2

Dit script heeft hetzelfde euvel als het script van team 1. Er is wel een mooie controle of de meegegeven parameter een getal is.

#!/bin/bash
getal="$1"

re='^[0-9]+$'
if ! [[ $getal =~ $re ]] ; then
   echo "Fout: Geen nummer" >&2; exit 1
fi
priemgetal=1;
for (( c=2; c<$getal; c++ ))
do
   let "remainder = $getal % $c"

   if [ $remainder -eq 0 ]; then
     echo "$getal is deelbaar door $c";
     priemgetal=0;
   fi
done
if [ $priemgetal -eq 1 ]; then
  echo "$getal is een priemgetal";
fi

Team 3

Dit script ontbindt keurig in factoren. En heel mooi… met behulp van de exit code kan worden vastgesteld of het een priemgetal is.

#!/bin/bash
if [[ "$#" -ne 1 || ! "$1" =~ ^[0-9]+$ || $1 -eq 0 ]]; then
	echo "usage: $0 INT" >&2
	echo "    where INT>0" >&2
	exit 1
fi
NUM=$1
I=2
while [[ "$I" -lt $1 ]]; do
	if [ "$((NUM%I))" -eq "0" ]; then
		echo $I
		NUM=$((NUM/I))
	else
		I=$((I+1))
	fi
done
[[ "$NUM" -ne 1 ]] || exit 1

Team 4

Script werkt juist, maar controleert niet of de invoer een getal is. Ook een tekst-parameter levert het resultaat ‘priemgetal’ op. Bijzonder toch!

#!/bin/bash
[[ $# -eq 0 ]] && { echo "Gebruik: ontbinden <getal>"; exit; }

noemer=2
getal=$1
factoren=1
while (( $noemer <= getal )); do
    rest=$(($getal%$noemer))
    if [ $rest -eq 0 ]; then
        echo "$noemer"
        getal=$((getal/noemer))
        noemer=2
        factoren=$((factoren+1))
    else
        noemer=$((noemer+1))
    fi
    done

[[ $factoren -lt 3 ]] && echo "Priemgetal!"
exit

Snelheid

De snelheid van de scripts is nogal verschillend. Bij het ontbinden van het getal 4536731 zijn de tijden:

team tijd
1 0m48.319s
2 1m15.288s
3 1m2.878s
4 0m0.053s
De snelheid van team4 is vooral te danken aan het slimmigheidje om bij een gevonden factor
verder te gaan met het getal dat overblijft na deling.