Python: Checking if a number is prime

I’ve been doing a lot of problem solving on Project Euler recently. If your not aware of Project Euler (PE) it is a website with lots of maths / programming based puzzles to solve. Many of the problems involve using or checking prime numbers, in many cases a sieve method would be applicable (see: Sieve of Eratosthenes for a clear explanation / animation).

However sometimes this is not necessary if you only require one prime number, or if memory limitations mean a sieve would be inconceivable. The following is the code I wrote to check if a number is prime or not in python. It tests upwards checking if the number is perfectly divisble, and as it does this it lowers the maximum number need to reach to stop as we know that if a number is not divisible by 2 then it will not be uniquely divisible (a repatition of a divislbe may exist) by anything greater than N/2

def isprime(number):
	if number<=1:
		return 0
	while check<maxneeded+1:
		if number%check==0:
			return 0
	return 1

I hope that this made sense, and is useful to someone. If anyone has any more efficient methods I would be happy to hear from you.

Check out my profile to see which problems I’ve completed. If you’ve completed any I haven’t please get in contact and give me some tips.

Mike sent a suggestion that I could speed up the program by ignoring all factors of 2, it could also propbably be sped up by looking at 3,4,5 .. etc until certain point.

def isprime(number):
	if number<=1 or number%2==0:
		return 0
	while check<maxneeded+1:
		if number%check==0:
			return 0
	return 1

So lets test the speed difference by doing 1,000 checks of the number 982,451,653 (known to be prime from this usefulsite)

Original Code: 9.99917411804 Seconds elapsed
Improved Code: 5.2977039814 Seconds elapsed

That’s approximately a factor of two speed increase, but this makes me think that a combination of the sieve method with this one may lead to an even further increase.

Read More

Partitions and disk space in linux

I’m sure there are many ways to see the partitions and corresponding diskspace in linux, but here is the method I found:

$df -m
Filesystem 1M-blocks Used Available Use% Mounted on
/dev/sda2 7513 5937 1576 80% /
tmpfs 1005 0 1005 0% /lib/init/rw
varrun 1005 1 1005 1% /var/run
varlock 1005 0 1005 0% /var/lock
udev 1005 1 1005 1% /dev
tmpfs 1005 1 1005 1% /dev/shm
/dev/sdc1 469453 353295 92311 80% /media/x
/dev/sdd1 1408345 979205 429141 70% /media/z

or visually:

df -m screenshot

I kept struggeling to remember what letters it was, as there are many two letter commands beginning with d in linux… (dc, dd, df, dh, do, dl, du). I now remember it, because ‘f’ is next to the ‘d’ key on my keyboard, and because df probably stands for disk-free.

For more information check out this site

Read More


Using the free command gives output something like this (-m just tells free to output in megabytes):

free -m
total used free shared buffers cached
Mem: 2013 1996 17 0 27 1381
-/+ buffers/cache: 588 1425
Swap: 956 0 956

This is useful but annoying as it doesn’t show you how much memory is actually free. Files that are used are kept in the ram (referred to as caching). If the memory is needed it is simply overwritten, however if the file is used again it is already in the memory which saves time.

I wrote a quick little bash line to get the actually memory in use or the actual memory free. I use grep to select the right line from the output of free, and then use awk to do the string manipulation and math.

Memory in use

free -m | grep Mem | awk ‘{x=$3-$7; print x}’

Memory free

free -m | grep Mem | awk ‘{x=$2-($3-$7); print x}’

Read More

apt – no public key error

If you add a new repository to apt (/etc/apt/sources.list) you may get the following error when running ‘sudo apt-get update’:

Reading package lists… Done
W: There is no public key available for the following key IDs:
W: You may want to run apt-get update to correct these problems

As you probably already guessed, running ‘sudo apt-get update’ will result in exactly the same problem. This is because the new repository’s key needs to verified. This is done by the following:

gpg –keyserver –recv [Key]
gpg –export [Key] | sudo apt-key add –

replace [Key] with the key you want to add

This can also be made slightly easier by using a bash variable:

gpg –keyserver –recv $1
gpg –export $1 | sudo apt-key add –

replace [Key] with the key you want to add

or as a bash script:

gpg –keyserver –recv $1
gpg –export $1 | sudo apt-key add –

ran by the following:

./key [key]

replace [Key] with the key you want to add
which then you could place in /bin so you could simply run

Script can be downloaded here

Read More

Bash: mass image and video conversions

Linux has many useful command line programs that will convert from one file format to another.

  • convert – converts images (part of ImageMagick)
  • convert input.jpg -resize 500×500 output.jpg

    converts input.jpg to output.jpg resized to 500 by 500 pixels

  • mencoder – converts video files
  • mencoder -ovc lavc -oac mp3lame -o output.avi input.flv

    converts input.flv to output.avi

    Now lets look at some bash:

    for i in *.jpg; do echo $i; done

    This is a for loop which will assign and iterate over a variable i to every item it finds that matches *.jpg in the current directory. It will simple echo the name of the file to the console and then finish. Only really useful for testing the command works, now lets put a conversion command in instead of the echo.

    for i in *.jpg; do convert “$i” -resize 500×500 “x_$i”; done

    This will take every jpg in the current directory resize it to 500 by 500 pixels and then save it as with and x_ prefixing the filename. You can get it to overwrite the current file by making the input and output file names equal (in this case it simple means removing x_ from the above code)

    Read More

    Streaming media from Linux to PS3

    I wanted to watch some of the videos that I have on my computer on my playstation 3, so that lead me to search for media server applications. I found out that you could set this up quite easily from within Windows Media Player, however as a linux user I knew there was probably a much better linux based solution available.

    After a few minutes of googling, I found a program called Mediatomb. It is avaliable at

    mediatomb is in the ubuntu repositories, so all that is needed to install it is:

    sudo apt-get install mediatomb

    All you need to do once it is setup is to open up the config file located at ~/.mediatomb/config.xml
    and to add the following below the <server> line

    <protocolInfo extend=”yes”/>

    then in the mappings section, add any file formats that you want to be forwarded. In this example .avi and .divx files have been added

    <extension-mimetype ignore-unknown=”no”>
    <map from=”avi” to=”video/x-divx”/>
    <map from=”divx” to=”video/x-divx”/>

    Once this is all done, you can run mediatomb, and it will give you an output like the following:

    MediaTomb UPnP Server version 0.11.0 –

    Copyright 2005-2008 Gena Batsyan, Sergey Bostandzhyan, Leonhard Wimmer.
    MediaTomb is free software, covered by the GNU General Public License version 2

    2008-08-13 23:46:19 INFO: Loading configuration from: /home/mat/.mediatomb/config.xml
    2008-08-13 23:46:19 INFO: Checking configuration…
    2008-08-13 23:46:19 INFO: Setting filesystem import charset to UTF-8
    2008-08-13 23:46:19 INFO: Setting metadata import charset to UTF-8
    2008-08-13 23:46:19 INFO: Setting playlist charset to UTF-8
    2008-08-13 23:46:19 INFO: Configuration check succeeded.
    2008-08-13 23:46:19 INFO: Initialized port: 49152
    2008-08-13 23:46:19 INFO: Server bound to:
    2008-08-13 23:46:20 INFO: MediaTomb Web UI can be reached by following this link:
    2008-08-13 23:46:20 INFO:

    The last line shows the information of use, using the ip address you can login to the web interface for the mediatomb server, from there you can add the folders you wish to be shared.

    Then on the PS3 or whatever device you are using, you should be able to access the files that you have shared. My PS3 automatically found the server but also had the option to scan for media servers. The only problem with the playstation is that it will refuse to play some files, but most of the videos I tried worked.

    Conclusion: Pretty dam cool

    The following link is a slightly better guide, than my brief overview
    P.S. Media tomb also shares images and music files etc… forgot to mention it.

    Read More