Fedora Linux Support Community & Resources Center

Go Back   FedoraForum.org > Fedora Resources > Guides & Solutions (Not For Questions)
FedoraForum Search

Forgot Password? Join Us!

Guides & Solutions (Not For Questions) Post your guides here (No links to Blogs accepted). You can also append your comments/questions to a guide, but don't start a new thread to ask a question. Use another forum for that.

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 18th November 2012, 11:30 PM
sea Offline
"Shells" (of a sub world)
 
Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,280
linuxfedorachrome
[BASH]: Prime Numbers

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=|| 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 $[ $] ];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
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass re-encode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161

Last edited by sea; 19th November 2012 at 07:45 PM.
Reply With Quote
  #2  
Old 18th November 2012, 11:49 PM
Adunaic Offline
Registered User
 
Join Date: Mar 2009
Location: Lancaster, UK
Posts: 928
linuxsafari
Re: [BASH]: Prime Numbers

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?
Reply With Quote
  #3  
Old 19th November 2012, 12:29 AM
sea Offline
"Shells" (of a sub world)
 
Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,280
linuxfedorachrome
Re: [BASH]: Prime Numbers

Thank you, i'll have a look into %.
As long you see:
Code:
echo
echo "Hope this helped :)"
echo
at the end, its all good. (you can scroll the displaying textarea)
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass re-encode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161
Reply With Quote
  #4  
Old 19th November 2012, 12:51 AM
stevea
Guest
 
Posts: n/a
linuxfirefox
Re: [BASH]: Prime Numbers

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).
Reply With Quote
  #5  
Old 19th November 2012, 08:38 AM
Skull One Offline
Registered User
 
Join Date: Jun 2010
Location: Lost...
Posts: 1,300
linuxredhatmozilla
Re: [BASH]: Prime Numbers

You can save some computationnal power by discarding the obvious multiples.
For instance, for num > 5:
Code:
case ${num:${#num}-1:1} in
     0|2|4|6|8|3|9|5)
           disgard num;;
     *)
           continue;;
esac
__________________
:confused:
Reply With Quote
  #6  
Old 19th November 2012, 10:45 AM
Adunaic Offline
Registered User
 
Join Date: Mar 2009
Location: Lancaster, UK
Posts: 928
linuxfirefox
Re: [BASH]: Prime Numbers

Quote:
Originally Posted by sea View Post
Thank you, i'll have a look into %.
As long you see:
Code:
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.
Reply With Quote
  #7  
Old 19th November 2012, 12:57 PM
stevea
Guest
 
Posts: n/a
linuxfirefox
Re: [BASH]: Prime Numbers

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


Code:
#!/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"
Reply With Quote
  #8  
Old 20th November 2012, 04:50 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,483
linuxfedorafirefox
Re: [BASH]: Prime Numbers

Here's a Perl version that calculates all the primes < 1,000,000 in about 5 seconds on my machine:
Code:
#!/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;
	}
}
__________________
OS: Fedora 25 x86_64 | Machine: HP Pavilion a6130n | CPU: AMD 64 X2 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #9  
Old 20th November 2012, 05:21 AM
sea Offline
"Shells" (of a sub world)
 
Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,280
linuxfedorachrome
Re: [BASH]: Prime Numbers

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?
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass re-encode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161
Reply With Quote
  #10  
Old 20th November 2012, 09:11 AM
weitjong Offline
Registered User
 
Join Date: Oct 2006
Location: Singapore, 新加坡
Posts: 986
macossafari
Re: [BASH]: Prime Numbers

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.

Code:
#!/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.
__________________
YaoWT - Leave no window unbroken ♪ (^。^) 
Reply With Quote
  #11  
Old 20th November 2012, 11:47 AM
marriedto51 Offline
Registered User
 
Join Date: Jul 2009
Location: England, UK
Posts: 966
linuxfirefox
Re: [BASH]: Prime Numbers

Quote:
Originally Posted by sea View Post
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).
Reply With Quote
  #12  
Old 21st November 2012, 12:21 AM
sidebrnz Online
Registered User
 
Join Date: Oct 2007
Location: Freedonia
Age: 67
Posts: 2,959
linuxfirefox
Re: [BASH]: Prime Numbers

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.
__________________
Registered Linux user #470359 and permanently recovered BOFH.

Any advice in this post is worth exactly what you paid for it.
Reply With Quote
  #13  
Old 21st November 2012, 06:10 AM
weitjong Offline
Registered User
 
Join Date: Oct 2006
Location: Singapore, 新加坡
Posts: 986
macossafari
Re: [BASH]: Prime Numbers

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.
__________________
YaoWT - Leave no window unbroken ♪ (^。^) 
Reply With Quote
  #14  
Old 21st November 2012, 07:24 AM
stevea
Guest
 
Posts: n/a
linuxfirefox
Re: [BASH]: Prime Numbers

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 ...
Quote:
[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 ....
Quote:
[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 ...
Quote:
[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
Quote:
[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.
Quote:
[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.
Quote:
[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 0m11.305s
user 0m10.935s
sys 0m0.005s
perl to 100million
Quote:
[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 1m59.252s
user 1m55.911s
sys 0m0.125s

Last edited by stevea; 21st November 2012 at 07:54 AM.
Reply With Quote
  #15  
Old 21st November 2012, 10:18 AM
marriedto51 Offline
Registered User
 
Join Date: Jul 2009
Location: England, UK
Posts: 966
linuxfirefox
Re: [BASH]: Prime Numbers

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!)
Code:
#!/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
Reply With Quote
Reply

Tags
bash, numbers, prime, script

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Program to find prime numbers renkinjutsu Programming & Packaging 9 4th September 2011 07:40 AM
BASH can't compare two numbers PompeyBlue Programming & Packaging 11 11th July 2010 12:55 AM
Not Ready for Prime TIme Avix Fedora Focus 14 27th March 2006 09:43 AM
FC5 Not Ready for Prime Time? bobw EOL (End Of Life) Versions 3 27th March 2006 05:15 AM


Current GMT-time: 06:35 (Monday, 27-03-2017)

TopSubscribe to XML RSS for all Threads in all ForumsFedoraForumDotOrg Archive
logo

All trademarks, and forum posts in this site are property of their respective owner(s).
FedoraForum.org is privately owned and is not directly sponsored by the Fedora Project or Red Hat, Inc.

Privacy Policy | Term of Use | Posting Guidelines | Archive | Contact Us | Founding Members

Powered by vBulletin® Copyright ©2000 - 2012, vBulletin Solutions, Inc.

FedoraForum is Powered by RedHat