Computer Science Programming Basics in Ruby

5.6 Example: Finding Prime Numbers

You now know enough to write numerous computer programs in Ruby, and we will soon finally be able to stop worrying about the details of a programming language and return to the fundamentals of computer science. In fact, at this point, you really know enough to compute mathematically just about anything that can be computed. To provide a little more practice with the topics we have discussed, let’s return to our prime number example. First we present a Ruby implementation (Example 5-7), and then we explain the algorithm illustrated in detail.

Example 5-7. Prime numbers

     1 # Initialize our counter
     2 i = 1
     3 
     4 # i: [0, 100]
     5 while (i <= 100)
     6   # Initialize prime flag
     7   prime_flag = true
     8   j = 2
     9   # Test divisibility of i from [0, i/2]
    10   while (j <= i / 2)
    11     # puts " i ==> " + i.to_s + " j ==> " + j.to_s
    12     if (i % j == 0)
    13       prime_flag = false
    14       # break
    15     end
    16     j = j + 1
    17   end
    18   # We found a prime!
    19   if prime_flag
    20     puts "Prime ==> " + i.to_s
    21   end
    22   # Increment the counter
    23   i += 1
    24 end

Recall that a number is considered prime if and only if its only divisors, commonly called factors, are 1 and itself. For example, 9 is not prime while 7 is. As hinted in Chapter 3, it is unnecessary to check for factors until you reach the actual number (minus one) since the largest divisor must be no greater than half the number itself. A prime number implementation can be optimized by using the knowledge that we can terminate the loop early. ...