[BASH]: Prime Numbers

[sea]

Heyas

Its been a while since i've done some math,
so out of curiousity and 'fun' i wanted to write a bash script doing that.

AFAIK: A prime number is defined by any number that is only dividable by 1 or itself.
AFAIK: Bash works only with integer numbers, which uses no coma seperation.

Prime Numbers are not EVEN
But 2 beeing the only expection!
So at first a think of a function that helps to me skip every even number (eg 4,8,18,100), to save some 'math power'.
So that function simply divides provided number by 2 and looks if the half number * 2 equals the original number.
I've modified the function so i can pass a 2nd argument which is used when i want to divide the number with something diffrent than 2.
Still thinking that (17/3)*3 is not 17 when counting with int values.

Getting the prime number
So to get the prime numbers i pass every uneven number to check if it by the prime function.
The prime function expects a prime number to be not even as long its dividing number is not 1 or itself.
So it divide the prime counter with every number until current one, and as long it is not even, it expects to be NON prime.

Ok... until i wrote this, i got my script fixed mainwhile., so copy paste from programming to guides & Solutions.
So lets share it for those with homeworks

PHP Code:

#!/bin/bash
#
#    Description:    Simply calculates prime numbers between min and max variable
#    Lisence:    GPL v3
#    Date created:    2012.11.18
#    Date changed:    2012.11.18
#    Written by:    Simon A. Erat, erat . simon æ gmail . com
    script_version=0.1
#
#    Variables
#
    prime_min=3
    prime_max=4000
    C=$prime_min
#
#    Title
#
    clear
    echo "Calculating prime numbers ($script_version)"
#
#    Subs
#
    isEven() { # NUM1 [ NUM2]
    # Check if number is even, if NUM2 is missing its divideing by 2.
    # Returns 0 for success, 1 otherwise.
        retval=1
        num=$1
        [ "" = "$2" ] && div=2 || div=$2
        check=$[ $num / $div ]
        [ $num -eq $[ $check * $div ] ] && retval=0
        return $retval
    }
    isPrime() { # NUM
    # Verifies all numbers from 2 to NUM-1
    # If none returns even, it returns 0, 1 otherwise
        retval=0
        count=2
        while [ $count -le $[ $1 - 1 ] ];do
            # We already skiped even numbers, so no need to use them now.
            if ! isEven $count 
            then    # Like: 15 / 3 = 5 = even
                isEven $1 $count && retval=1  && break
            fi
            ((count++))
        done
        return $retval
    }
#
#    Display
#
    printf "\n\rPrime numbers from $prime_min to $prime_max\n:: Calculating... "
    while [ $C -le $prime_max ];do
        # Dont need to check even numbers
        if ! isEven $C 
        then    # Is it a prime number?
            if isPrime $C
            then    printf " $C"
            #else    printf "."
            fi
        fi
        ((C++))
    done
    echo
    echo
    echo "Hope this helped :)"
    echo 


Hope this helps or you have fun with it

[Adunaic]

Could you use the mod operator (%) to check if a number is even? (n%2; returns 0 if n is even. I think thats the correct syntax. Also some code missing from the end?

[sea]

Thank you, i'll have a look into %.
As long you see:

echo
echo "Hope this helped :)"
echo

at the end, its all good. (you can scroll the displaying textarea)

[stevea]

Ehh

2 is a prime and its even !

Aside from 2, all primes are odd (2n+1)
Aside from 2 & 3, all primes are of the form (6n-1) or (6n+1)
Aside from 2,3,5,7,11,13 all primes are of the form (30n +-{1,7,11,13})

That sort of thinking doesn't reduce the computation very much.
Consider that all non-primes 'N' have a prime factor <= sqrt(N).
Examine the more advanced sieves (the sieve of atkin).

[Skull One]

You can save some computationnal power by discarding the obvious multiples.
For instance, for num > 5:

case ${num:${#num}-1:1} in
     0|2|4|6|8|3|9|5)
           disgard num;;
     *)
           continue;;
esac

[Adunaic]

Originally Posted by sea

Thank you, i'll have a look into %.
As long you see:

echo
echo "Hope this helped :)"
echo

at the end, its all good. (you can scroll the displaying textarea)

Sorry, I was looking at it on my phone and it did not sho that I could scroll in the code.

[stevea]

Here. This calculates primes <250000 in about the same times as the OPs does <4000.
It's still not good.

#!/bin/bash
# not very good primes program

# vars ------------------------------------------------------------
prime_max=250000
# initial values, do not change
cmax=1
cmaxsqr=1

# functions -------------------------------------------------------
# is arg1 a multiple of arg2 ?
isMultiple() { return  $((($1%$2) != 0)) ; }
    
# is the next consecutive prime 
isNextPrime() {
    while [ $1 -gt $cmaxsqr ]
    do
	((cmax++))
	cmaxsqr=$(($cmax * $cmax))
    done
    
    for((count=3; count<=cmax; count+=2))
    do
        #  isMultiple $1 $count 
        # inline the function
	[ $(($1%$count)) -eq 0 ]  && return 1
    done
    return 0
}

# --- main -------------------------------------------------------

clear
echo "Calculating prime numbers ($script_version)"
printf "\n\rPrime numbers to $prime_max\n:: Calculating...  2"

for((i=3; i<= $prime_max; i+=2))
do
    isNextPrime $i && printf " $i"
done
printf "\ndone"

[RupertPupkin]

Here's a Perl version that calculates all the primes < 1,000,000 in about 5 seconds on my machine:

#!/usr/bin/perl
my $UPPER = 1000000;
my $sieve = "";
GUESS: for (my $guess = 2; $guess <= $UPPER; $guess++) {
	next GUESS if vec($sieve,$guess,1);
	print "$guess\n";
	for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += $guess) {
		vec($sieve,$mults,1) = 1;
	}
}

[sea]

WTF, it speeds up...
it took more time to calculate the first 4 numbers, than the rest of the 900'000.

And to make sure, a sieve is a synonym for filter?

[weitjong]

That is not surprising. It is easier to find low prime numbers then the high ones and when it does the algorithm needs to "mark" all its multiplies as non-prime. The first iteration for the first prime number (i.e. 2) practically has to mark the bit for all the even numbers within UPPER limit.

---------- Post added at 04:11 PM ---------- Previous post was at 03:19 PM ----------

With that in mind, below revised version runs a tad faster than original one from Rupert.

#!/usr/bin/perl
my $UPPER = 1000000;
my $sieve = "";
print "2\n";
for (my $guess = 3; $guess <= $UPPER; $guess+=2) {
	next if vec($sieve,$guess,1);
	print "$guess\n";
	for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += $guess) {
		vec($sieve,$mults,1) = 1;
	}
}

Using my Intel i7, the original takes ~0.64 sec, while the revised one takes ~0.5 sec.

[marriedto51]

Originally Posted by sea

And to make sure, a sieve is a synonym for filter?

This one is the Sieve of Eratosthenes.

In common english, sieve and filter are nearly the same of course. But "sieve" seems to be the word that has historical precedence in this context (and "filter" has a very specific meaning in the mathematics of ordered sets).

[sidebrnz]

You can speed things up, weitjong, by only starting your marking multiples of a new prime with its square, because all smaller ones will already be marked. And that means that once you've checked the square root of your limit you can stop because all the primes will be marked.

[weitjong]

Believe it or not, I had attempted to do just that the first thing after reading Rupert's post. I soon realized Rupert's original version is already in optimized form. It already starts the first mults with the square of the prime itself. Although the marking could stop at the square root of the UPPER limit, the outer for-loop itself still has to iterate until reaching the UPPER limit to print out the results themselves. Furthermore, the marking loop (the inner for-loop) stops automatically after the $guess reaches the square root of the UPPER limit.

Unless, we split the marking and printing into two separate loops. The marking loop stops at square root while the printing one goes all the way.

[stevea]

Hmm - If you want fast, but not bash there are lot's better solutions than perl.
That was never the topic.

This one uses pari-gp package ...

[stevea@hypoxylon EP]$ export MAX=1000000; time ( echo "primes(primepi($MAX))"| gp -p $MAX > /dev/null)
real 0m0.028s
user 0m0.021s
sys 0m0.006s

On same hardware ....

[stevea@hypoxylon tmp]$ time ./perljunk >/dev/null
real 0m1.054s
user 0m1.023s
sys 0m0.003s

Not bad for an interpreted language, but ... the question of algorithm is key.

As we go to larger upper bounds ....

Pari with a 10 million upper bound ...

[stevea@hypoxylon tmp]$ export MAX=10000000; time ( echo "allocatemem(500000000) ; primes(primepi($MAX))"| gp -p $MAX >/dev/null )
real 0m0.163s
user 0m0.130s
sys 0m0.027s

Pari at 100 million

[stevea@hypoxylon tmp]$ export MAX=100000000; time ( echo "allocatemem(500000000) ; primes(primepi($MAX))"| gp -p $MAX > /dev/null )
real 0m1.497s
user 0m1.150s
sys 0m0.286s

Pari computes all primes to one billion in ~32 seconds here.

[stevea@hypoxylon tmp]$ export MAX=1000000000; time ( echo "allocatemem(5000000000) ; primes(primepi($MAX))"| gp -p $MAX > /dev/null )
real 0m32.373s
user 0m10.931s
sys 0m5.691s

vs the perl script modified to 10 mill.

[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 0m11.305s
user 0m10.935s
sys 0m0.005s

perl to 100million

[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 1m59.252s
user 1m55.911s
sys 0m0.125s

[marriedto51]

Well, if we're going to switch to a library written in a compiled language by world-leaders in computational number theory, then no doubt we can get some better results in terms of speed

At the opposite extreme, in case you've not seen it, here's an insane way to check for primality... (Works for anything from 2 upwards; no error checking on the input!)

#!/bin/bash
str=''
for (( i = 0; i < "$1" ; i++ )); do
    str="$str"1
done
if echo "$str" | grep -q -E '^(11+)\1+$'; then
    echo "$1 is not prime"
else
    echo "$1 is prime"
fi