38

I have the following working code:

largest_prime=1
for number_under_test in {1..100}
do
  is_prime=true
  factors=''
  for ((divider = 2; divider < number_under_test-1; divider++));
  do
    remainder=$(($number_under_test % $divider))
    [ $remainder == 0 ] && [ is_prime ] && is_prime=false && factors+=$divider' '
  done
  [ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test
done
printf "\nLargest Prime= $largest_prime\n"

This code runs quickly is 0.194 seconds. However I found the && is_prime= false a bit hard to read and it could look (to the untrained eye) as if it was being tested rather than being set which is what it does. So I tried changed the && into an if...then and this works - but is 75 times slower at 14.48 seconds. It's most noticeable on the higher numbers.

largest_prime=1
for number_under_test in {1..100}
do
  is_prime=true
  factors=''
  for ((divider = 2; divider < number_under_test-1; divider++));
  do  
    remainder=$(($number_under_test % $divider))
    if ([ $remainder == 0 ] && [ $is_prime == true ]); then
      is_prime=false
      factors+=$divider' '
    fi  
  done
  [ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test
done  
printf "\nLargest Prime= $largest_prime\n"

Is there any was to have the clarity of the block without the slowness?

Update (1/4/2015 10:40am EST)

Great feedback! I am now using the following. Any other feedback ?

largest_prime=1
separator=' '
for number_under_test in {1..100}; {
  is_prime=true
  factors=''
  for ((divider = 2; divider < (number_under_test/2)+1; divider++)) {
    remainder=$(($number_under_test % $divider))
    if [ $remainder == 0 ]; then
      is_prime=false
      factors+=$divider' '
    fi
  } 
  if $is_prime; then
    printf "\n${number_under_test} IS prime\n\n"
    largest_prime=$number_under_test
  else
    printf "${number_under_test} is NOT prime, factors are: "
    printf "$factors\n"
  fi
}
printf "\nLargest Prime= $largest_prime\n"
  • 1
    On a sidenote, running your script prints that Largest Prime= 100 on my computer. – Giulio Muscarello Jan 3 '15 at 18:09
  • 3
    Also on a sidenote, if you're interested in efficiency, one trivial way to improve this would be to only iterate up to number_under_test/2 instead of up to number_under_test-1: No factor of a number n is greater than n/2, so you will still find all factors for non-prime numbers by doing this. (Also if you were only interested in testing for primeness, it would be sufficient to iterate up to sqrt(n), but Bash doesn't have a built-in function to compute square roots anyway.) – Malte Skoruppa Jan 4 '15 at 0:42
  • Matte, good point (+1). The only change was that didn't work for the number 4 so I had to make it (number_under_test/2)+1 to allow for that – Michael Durrant Jan 4 '15 at 14:36
  • 1
    In your updated version, the braces {} are not really needed after the then clause because the then already serves as a grouping operator (along with elif, else, or fi). In fact, in some shells, you could write, for example, for i in 1 2 3; { echo $i; } with no do or done. – Jonathan Leffler Jan 4 '15 at 15:27
  • 1
    +1 Jonathan, I made those changes and updated the update – Michael Durrant Jan 4 '15 at 15:40
66

That's because you're spawning a sub-shell every time:

if ([ $remainder == 0 ] && [ $is_prime == true ]); then

Just remove the parentheses

if [ $remainder == 0 ] && [ $is_prime == true ]; then

If you want to group commands, there's syntax to do that in the current shell:

if { [ $remainder == 0 ] && [ $is_prime == true ]; }; then

(the trailing semicolon is required, see the manual)

Note that [ is_prime ] is not the same as [ $is_prime == true ]: you could write that as simply $is_prime (with no brackets) which would invoke the bash built-in true or false command.
[ is_prime ] is a test with one argument, the string "is_prime" -- when [ is given a single argument, the result is success if the argument is non-empty, and that literal string is always non-empty, hence always "true".

For readability, I would change the very long line

[ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test

to

if [ $is_prime == true ]; then
  echo "${number_under_test} is prime!"
else 
  echo "${number_under_test} is NOT prime (factors= $factors)"
  # removed extraneous [ $is_prime == true ] test that you probably
  # didn't notice off the edge of the screen
  largest_prime=$number_under_test
fi

Don't underestimate whitespace to improve clarity.

  • 1
    there is a Typo - largest_prime=$number_under_test should be in the then branch (the same error is in the original) – JJoao Jan 3 '15 at 19:31
  • 1
    It's also worth noting that in bash, zsh, et al, [ is invoking a program literally called [, whereas [[ is implemented in the shell - hence it'll be faster. Try time for ((i = 0; $i < 1000; i++)); do [ 1 ]; done and compare to [[. See this SO question for further info. – kirb Jan 4 '15 at 11:55
  • 2
    bash implements [, it's a builtin. From a shell prompt, type type -a [ and help [ – glenn jackman Jan 4 '15 at 14:03
  • @glennjackman Wow; wasn't aware of that. I assumed it was still the case because which [ still returns /usr/bin/[. I also just realised that I implied zsh was the same; for me that does tell me it's a builtin. But then... why is [[ faster? – kirb Jan 4 '15 at 17:27
  • 2
    @glennjackman command -v is another good which alternative; see also here. – Abbafei Jan 5 '15 at 7:40
9

I think you're working way too hard on that function of yours. Consider:

unset num div lprime; set -- "$((lprime=(num=(div=1))))"
while [     "$((     num += ! ( div *= ( div <= num   ) ) ))" -eq \
            "$((     num *=   ( div += 1 )   <= 101   ))" ]    && {
      set   "$(( ! ( num %      div )         * div   ))"     "$@"
      shift "$(( !    $1 +    ( $1 ==  1 )    *  $#   ))"
}; do [ "$div" -gt "$num" ] && echo "$*"      
done

Shell arithmetic is pretty capable of evaluating integer conditions on its own. It rarely needs too many tests and/or outside assignments. This one while loop duplicates your nested loops fairly well:

It doesn't print as much, of course, I didn't write all that much, but, for example setting the ceiling to 16 rather than 101 as is written above and...

2
3
4 2
5
6 3 2
7
8 4 2
9 3
10 5 2
11
12 6 4 3 2
13
14 7 2
15 5 3

It's definitely doing the work. And it requires very little else to approximate your output:

...
do [ "$div" -eq "$num" ] && shift &&
   printf "$num ${1+!}= prime.${1+\t%s\t%s}\n" \
          "factors= $*"                        \
          "lprime=$(( lprime = $# ? lprime : num ))"
done

Just doing that rather than the echo and...

1 = prime.
2 = prime.
3 = prime.
4 != prime.     factors= 2      lprime=3
5 = prime.
6 != prime.     factors= 3 2    lprime=5
7 = prime.
8 != prime.     factors= 4 2    lprime=7
9 != prime.     factors= 3      lprime=7
10 != prime.    factors= 5 2    lprime=7
11 = prime.
12 != prime.    factors= 6 4 3 2        lprime=11
13 = prime.
14 != prime.    factors= 7 2    lprime=13
15 != prime.    factors= 5 3    lprime=13

This works in busybox. It is very portable, fast, and easy to use.

Your subshell issue is going to occur in most shells, but it is, by far, most acute in a bash shell. I alternated between doing

( [ "$div" -gt "$num" ] ) && ...

...and the way I wrote it above in several shells for a ceiling of 101 and dash did it without the subshell in .017 seconds and with the subshell in 1.8 seconds. busybox .149 and 2, zsh .149 and 4, bash .35 and 6, and ksh93 in .149 and .160. ksh93 does not fork for subshells as the other shells must. So maybe the problem is not so much the subshell as it is the shell.

  • What's the advantage of [ "$((...))" -eq "$((...))" ] over (( (...) == (...) ))? Is the latter less portable? – ruakh Jan 4 '15 at 17:33
  • @ruakh - portability, speed, reliability. [ "$((...))" -eq "$((...)) ] works in shells that don't take 15 seconds to run the program, and the other doesn't. If the advantage of one over another is questionable at all, then that can only give the edge to the former, which means there is never a good reason to use (( (...) == (...) )). – mikeserv Jan 4 '15 at 19:09
  • Sorry, but your reply seems to assume that I already have a detailed knowledge of shell support for (( ... )). I'm flattered, but I do not have that detailed knowledge. (Remember, I'm the one who just asked if (( ... )) is less portable.) So I really can't make sense of your reply. :-/ Could you be a bit more explicit? – ruakh Jan 4 '15 at 19:27
  • @ruakh - I'm sorry... I didn't see that you were asking if it was more portable, just how it was advantageous - which is why I replied about portability. Anyway, the "$((...))" is POSIX-specified and the other is a shell extension. POSIX shells are pretty capable. Even dash and posh will correctly handle branch tests like "$((if_true ? (var=10) : (var=5) ))" and always assign $var correctly. busybox breaks there - it always evals both sides regardless of $if_true's value. – mikeserv Jan 4 '15 at 19:37
  • @ruakh - oh man. I must be a little off today... it says right there... is the latter less portable? I didn't see that before, I guess...? – mikeserv Jan 4 '15 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.