Saturday, June 14, 2008
Shell Script To Produce Prime Numbers On Linux And Unix
Hey There,
You might recall (quite a while back) the last time we put out a Linux or Unix script involving a somewhat-complex mathematical formula. The most recent post had to deal with factorial generation and the only other mostly-math post we did prior to that was about generating Fibonacci numbers up to any user-defined limit.
Today we're going to look at a similar issue, and develop a similar script. This time we'll work on something that, on its face, seems a bit easier to figure out. Today we're going to create a script that will list out all "prime" numbers up to a user-defined limit. We'll stay away from "relative primes" since (by definition) any two numbers, that aren't primes, share a greatest common factor (Sometimes referred to as the lowest common denominator in fractions) of 1. So non-prime numbers like 9 (1 x 3 x 9) and 25 (1 x 5 x 25) are considered relative primes. The definition basically applies to any numbers that aren't primes. You could easily derive those just by removing all the prime numbers from the positive integer set you define when you invoke the script, which can be easily done, like this:
host # ./primes.sh 100
Composite numbers are the result of the multiplication of prime numbers. We'll take a look at scripting out composites for our next post. It should be a natural extension of today's script.
It's interesting to note, though, that the number 1 is not considered a prime, because it only has one factor: itself. All other numbers, that are available for prime status, have two factors: themselves and themselves divided by 1 (with the result being a positive integer). Of course, the number 1 divided by 1 is zero; therefore, it only has one factor and it's not a prime. It is also not considered a composite. We'll be avoiding the dreaded zero today, as well, since it's neither a prime nor a composite either.
With all that muck out of the way (I hope ;), let's take a look at defining prime numbers on a formula-based scale. There is an excellent reference online at mathforum.org that goes into detail about many different ways (some better, some worse) to go about deriving primes to the nth degree. For our purposes, we're going to dispense with the Greek alphabet and look at solving the problem as purely as possible, even though that might not be the "most efficient" way to do it. Sometimes (especially if you're not a math wizard, like me), understanding how to generate numbers that meet certain criteria, is more important than applying advanced mathematical formulae which, for all I know, may or may not even be completely valid. If you're ever up for twisting your brain into a knot, try to absolutely prove any advanced mathematical formula. For kicks, ask an advanced mathemetician to do the same ;)
For those of you who are curious (since there are so many theorems out there), our script today is based on Wilson's Theorem, which basically states:
An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p
In other words, if you take your chosen number, subtract 1 from that, get the factorial value (which we've gone through in more detail in our post regarding factorial generation ) of the resulting subtraction and then add 1 to it, the number is only prime if the modulus (or remainder) of that resulting number's division by the original number is equal to 0 (or, depending on how you prefer to think of it, if the resulting number is absolutely divisible by the original number).
I hope you enjoy this script. I wangled the factorial function so that it's quite a bit faster than the "bash" method shown in our factorial generation post from earlier on. In fact, here's a look at the time savings from Linux running on a now-obsolete PC :)host # time ./primes.sh.bak 35
Generating Prime Numbers Up To 35
2 3 5 7 11 13 17 19 35
All Set!
real 3m21.994s
user 0m18.445s
sys 0m40.857s
host # time ./primes.sh 35
Generating Prime Numbers Up To 35
2 3 5 7 11 13 17 19 35
All Set!
real 0m8.173s
user 0m1.464s
sys 0m2.407s
Note that this script can't find the highest prime number (I don't think anyone's figured that out yet), but it can figure out the highest prime number your system is capable of calculating. Close enough ;)
Cheers,
Creative Commons License
This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License #!/bin/bash
#
# primes.sh - find all prime numbers up to a certain number
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#
factorial () {
local factorial_count=1ドル
if [ "$factorial_count" -eq 0 ]
then
factorial_count=1
fi
for (( factor=$((factorial_count -1)); $factor >= 1; --factor ))
do
factorial_count=$(($factorial_count * $factor))
done
echo $factorial_count
}
prime_number () {
local prime=1ドル
p_minus_1=$(($prime - 1))
fact_p_minus_1=`factorial "$p_minus_1"`
fact_plus_1=$(($fact_p_minus_1 + 1))
echo $fact_plus_1
}
highest_number=1ドル
if [ -z $highest_number ]
then
echo
echo "Usage: 0ドル highestNumber"
echo
exit 1
fi
if [ $highest_number -eq 0 ]
then
echo
echo "Sorry. 0 is not a prime number"
echo
exit 0
elif [ $highest_number -eq 1 ]
then
echo
echo "Sorry. 0 and 1 are not prime numbers"
echo
exit 0
fi
echo "Generating Prime Numbers Up To $highest_number"
if [ $highest_number -eq 2 ]
then
echo
echo -n "2"
else
echo
echo -n "2 3 "
fi
count=4
while [ $count -le $highest_number ]
do
prime_return=`prime_number "$count"`
prime_test=$(($prime_return % count))
if [ $prime_test -eq 0 ]
then
echo -n "$count "
fi
count=$(($count + 1))
done
echo
echo
echo "All Set!"
echo
exit 0
, Mike
Tuesday, November 6, 2007
Weird Obsession With Fibonacci Numbers - Brute Force Scripting!
Every once in a while, I cruise shell, perl and other unix/linux forums and try to help people out by answering questions and, inevitably, learning more than I impart.
The reason I mention this is the reason for today's post and it's strange title. For some reason, lately, lots of folks have been looking for code to list out Fibonacci numbers up to the highest number equal to or lesser than the one given on the command line as an argument. Of course, I smell a homework assignment here, but, why not just do it anyway?
Of course, even though I'd heard of the numbering sequence and formula, I looked at Wikipedia's Definition to make sure I remembered the sequencing correctly.
Then I thought I'd write a script as fast as I could to complete this task. It reminded me again of another very interesting principle. You can get a lot done in a very short period of time by being totally inefficient. It's especially o.k. if it's not your homework that you're doing ;)
For example, take this script that I whipped up in a few minutes. It takes an argument of one number (the outer delimiter) and it will print out all the Fibonacci numbers up to that argument value, unless that number value isn't a Fibonacci number, in which case it will print up to the last Fibonacci number less than that argument.
Creative Commons License
This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
The incredibly lame script:
#!/bin/ksh
#
# 2007 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#
final_number=1ドル
if [ -z $final_number ]
then
echo "No delimiter given. Exiting"
exit 1
fi
if [ $final_number -eq 0 ]
then
print "0"
exit 0
elif [ $final_number -eq 1 ]
then
print "0 1 1"
exit 0
else
print -n "0 "
first_number=1
fib=1
fi
start=1
while [ $fib -lt $final_number ]
do
if [ $start -eq 1 ]
then
print -n "1 "
last_number=0
next_number=1
start=0
fi
let fib=$last_number+$next_number
last_number=$next_number
next_number=$fib
if [ $fib -le $final_number ]
then
print -n "$fib "
fi
done
echo
exit 0
sample output:
$ ./fibo.sh 100000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025
Less than a page of code and not much thought put into making an efficient script. I decided to call it "Brute Force Scripting." Hey; sometimes your time is better spent not worrying about making things look pretty. If you get the job done and it's your job to get the job done, getting the job done is job number one ;)
, Mike
linux unix internet technology
affiliate program