Friday, April 4, 2008

Generating prime numbers in Ruby, Python and Perl

If you need to generate prime numbers, the classic algorithm is the Sieve of Eratosthenes. Both the Sieve and a simpler, but slower method (the one shown here) are discussed in Mastering Algorithms with Perl, by Orwant, Hietaniemi, and Macdonald (O'Reilly, 1999).

Here are the equivalent Ruby, Python and Perl scripts.

As with all of my scripts, the following disclaimer applies. Each of these three scripts are provided by its creator, Jules J. Berman, "as is", without warranty of any kind, expressed or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. in no event shall the author or copyright holder be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software.

For information about using Ruby for biomedical projects, you may want to read my recently published book:

Ruby Programming for Medicine and Biology


For information about using Perl for biomedical projects, you may want to read my recently published book:

Perl Programming for Medicine and Biology


Here is the Ruby script:

#!/usr/local/bin/ruby
state = Numeric.new
print "2,3,"
(4..10000).each do
|i|
(2..(Math.sqrt(i).ceil)).each do
|thing|
state = 1
if (i.divmod(thing)[1] == 0)
state = 0
break
end
end
print "#{i}\," unless (state == 0)
end
exit


Here is the equivalent Python script:

#!/usr/local/bin/python
import math
print "2,3,"
state = 1
for i in range(4, 10000):
upper = math.sqrt(i)
upper = int(upper)
for thing in range(2, upper):
state = 1
if (i % thing == 0):
state = 0
break
if (state == 1):
print i,
exit


Here's the equivalent Perl script.

#!/usr/local/bin/perl
print "2,3,";
for($i=4;$i<10000;$i++)
{
for $thing (2 .. int(sqrt($i)))
{
$state = 1;
if ($i % $thing == 0)
{
$state = 0;
last;
}
}
print "$i\," unless ($state == 0);
}
exit;

Sample output of the scripts is available.

The scripts are pretty straightforward. A prime number cannot be the product of two integers. We test each number up to 10,000 to determine if it is a prime number. If the number is prime, then there will be no smaller number that will divide into the number with a remainder of 0. So we test each number smaller than the number, to see if it divides into the number with anything other than a zero remainder. If not, then the number is a prime.

We stop when we get up to the square root of the number. If there were an integer larger than the square root of the number, which could be multiplied by another integer to give the number, then the other integer would need to be smaller than the square root of the number (otherwise, the two integers would produce a product larger than the number). But we've already tested all of the numbers smaller than the square root of the number, and they all yielded a non-zero remainder. So we don't need to test the integers greater than the square root of the number.

- Jules J. Berman, Ph.D., M.D. tags: prime numbers, prime number generation, calculating prime numbers, ruby programming, perl programming, python programming
Science is not a collection of facts. Science is what facts teach us; what we can learn about our universe, and ourselves, by deductive thinking. From observations of the night sky, made without the aid of telescopes, we can deduce that the universe is expanding, that the universe is not infinitely old, and why black holes exist. Without resorting to experimentation or mathematical analysis, we can deduce that gravity is a curvature in space-time, that the particles that compose light have no mass, that there is a theoretical limit to the number of different elements in the universe, and that the earth is billions of years old. Likewise, simple observations on animals tell us much about the migration of continents, the evolutionary relationships among classes of animals, why the nuclei of cells contain our genetic material, why certain animals are long-lived, why the gestation period of humans is 9 months, and why some diseases are rare and other diseases are common. In “Armchair Science”, the reader is confronted with 129 scientific mysteries, in cosmology, particle physics, chemistry, biology, and medicine. Beginning with simple observations, step-by-step analyses guide the reader toward solutions that are sometimes startling, and always entertaining. “Armchair Science” is written for general readers who are curious about science, and who want to sharpen their deductive skills.