Those that read my blogs regularly will know that I’ve had a bit of a recent obsession with prime numbers. I am really not sure why, but I have been doing a lot of programming with them. My original method had been to use modulus and check if a number was divisible by any already known prime numbers. I wrote this in Java and it it took an hour to generate all the primes up to 10,000,000. My next approach was to write a small Python program that used the Sieve of Eratosthenes where by you loop through the multiples of each number marking them as non-prime. This method works well but it is still quite slow.
My next approach, therefore, is to use the Sieve of Atkin. This is a relatively modern method that is highly efficient. Here I have implemented it in C++:
using namespace std;
int main (int argc, char* argv)
//Create the various different variables required
int limit = 1000000;
int root = ceil(sqrt(limit));
int insert = 2;
primes = 2;
primes = 3;
for (int z = 0; z < limit; z++) sieve[z] = false; //Not all compilers have false as the default boolean value
for (int x = 1; x <= root; x++)
for (int y = 1; y <= root; y++)
//Main part of Sieve of Atkin
int n = (4*x*x)+(y*y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
n = (3*x*x)+(y*y);
if (n <= limit && n % 12 == 7) sieve[n] ^= true;
n = (3*x*x)-(y*y);
if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
//Mark all multiples of squares as non-prime
for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
//Add into prime array
for (int a = 5; a < limit; a++)
primes[insert] = a;
//The following code just writes the array to a file
sprintf(filename, "primes_%d.txt", limit);
for (int a = 0; a < insert; a++) file << primes[a] << ((a == insert-1) ? "" : "\n");
cout << "Written to file.\n";
This method works incredibly well and is capable of producing primes in fractions of a seconds. Click here to download the source code.
Kinect is cool to a certain extent. It may be an XBOX gadget but the idea behind it is pretty much there – you dance around and the sensor feeds your movements back to the game. Microsoft essentially aim to produce the most diverse gaming experience possible and it has been very popular with social/casual gamers however it has not been as popular with the more hard core members of the community. Ideally it should have arrived a few years previously before the Wii was launched, and if that had happened Microsoft would easily have an XBOX in 1/3 of homes.
Kinect has been around since last year and so rumors are beginning to emerge about Kinect 2. The new Kinect would be released early next year and would have a dramatically improved sensor – the visible light camera on the current model is 640 by 480 and the infra-red sensor is 320-240. Clearly this will need to be improved before the release of the next model. If it had a higher resolution (and faster chip?) it may be able to pick up facial movements better, potentially allowing for lip reading.
The other thing to talk about with Kinect is a more official event. Microsoft have announced a scheme called ‘The Kinect Accelerator’. They plan to sponsor ten start-ups with $20,000 and office space to come up with a viable business use of Kinect, including everything from XBOX games to public galleries. The idea is interesting and no doubt it will be successful, but I would doubt that Microsoft will get all their money back.
When working with arrays a common problem is to implement a sorting algorithm so that you can get all the data in order. Most programming languages provide this functionality however it is important to know how to do it. The most simple algorithm to work with would be a Bubble sort, where you go through a list swapping the values into the correct order:
7 3 9 2
3 7 9 2
3 7 2 9
3 2 7 9
2 3 7 9
This isn’t too bad an algorithm and it is guaranteed to get everything in the correct order in the end. However, imagine how slow this would be if you had a few million numbers to sort through. Pretty slow.
The alternative, therefore, is to use a Quicksort algorithm. The idea behind it is take a list of numbers and pick a random number in the list. The list is then put into two groups – numbers less than the randomly selected and numbers more than or equal to the number selected. These groups are then sorted again and joined together.
Here is a source code example written in Python*:
for i in range(0, len(arrayToCheck)-1):
if arrayToCheck[i] > arrayToCheck[i+1]: return False
if sorted(arrayToSort) or len(arrayToSort) == 1: return arrayToSort
r = arrayToSort[random.randint(0, len(arrayToSort)-1)]
less = 
more = 
for a in arrayToSort:
if a < r: less.append(a)
return quicksort(less) + quicksort(more)
Here is how the algorithm works:
- We import the random module to generate random numbers
- The sorted function loops through the array checking to see if the current number is smaller than the previous number (we are sorting into ascending order) and if it isn’t return False
- At the top of the quicksort function we check if the array has already been sorted or if it is only one item long
- We pick a random number from the array
- We create two arrays, one for smaller numbers and one for larger and equal numbers
- We go through each value in the array and put into the appropriate new array
- We run the function on each array and put them together
This process is generally very fast – with Python I was achieving a couple of seconds for arrays with over 1,000,000 values in them – although I have achieved less with the algorithm in Java. This particular algorithm isn’t always wholly efficient because we are having to store a lot of extra data. You’ll generally find that the algorithm that is shipped with a programming language is capable of sorting in place, meaning that it doesn’t have to create new arrays.
*I have used Python because it is an easy to understand language and doesn’t require too much code. I know that it is easier to write in other languages and often more efficient.
The above map shows how programming languages have evolved and influenced each other. Try as I might, everything seemed to come back to either Fortran or Assembly. Most languages are, however, influenced by C, even if it is indirectly.
We are going to Mars! NASA have launched their Atlas 5 rocket which contains the rover Curiosity to Mars. The probe is on a mission to explore the Martian environment and try and discover microbes. It is by far the most advanced rover that has been sent to Mars or even into space. The mission has been going on for just over an hour, NASA’s website kindly tells us.
The press release also gives useful information on what is on the rover, which includes various cameras, a robotic arm and a computer that uses artificial intelligence. NASA are aiming for the rover to be on Mars and exploring by August 2012.
NASA are pretty excited about the launch because the main is to explore and identify habitable environments on Mars. It is also a lot bigger than previous rovers and larger. NASA have provided a table comparing Curiosity with Spirit/Opportunity (Explorer rovers):
- Heat shield diameter
- Curiosity: 4.5 meters
- Explorer: 2.65 meters
- Designed to work for
- Curiosity: 98 Earth weeks
- Explorer: 13 Earth weeks
- Number of instruments:
- Curiosity: 10
- Explorer: 5
- Robotic arm length:
- Curiosity: 2.1 meters
- Explorer: 0.8 meters
- Curiosity: Guided entry, sky crane
- Explorer: Ballistic entry, air bags
- Power supply:
- Curiosity: Multi-mission radioisotope thermoelectric generator
- Explorer: Photo voltaic cells
- Curiosity: Pair, 200Mhz, 250MB of RAM, 2GB flash memory, VxWorks
- Explorer: Single, 20Mhz, 128MB of RAM, 256MB flash memory, VxWorks
The last stat about the computer worries me. We are sending a revolutionary rover to Mars that has less computing power than an average computer made in 1995. Ironically the Raspberry Pi – which costs $25 – is four times faster. For the first time in a while I am truly worried about the US government if they can only afford to send a $10-ish computer to Mars.
Those of me that know me well will know that I’m not that great at design. That is to say that I can design fluid and dynamic user interfaces, I’m just rubbish at designing color schemes. Thankfully there is a fix for this thanks to many online tools.
The first and best tool is Adobe’s Kuler. The tool allows you to select one color and it will then build up a color scheme of colors like that color or that match it. Another new feature is that it allows you to select an image and it will generate a color scheme from that. I have found that it is incredibly easy to use and it also provides information in various different color formats meaning that you will get a useful color out of it.
ColoRotate is an alternative to Kuler which offers similar functionality however I found it a little more difficult as you have to spin a 3D color representation. The tool is probably most useful as a plugin in Fireworks and Photoshop however the browser version is a bit of a pain
The third tool that is OK is the aptly named Color Scheme Designer. It isn’t as well designed as ColoRotate or Kuler, but it does the job at picking colors. There are less options as well, but it is usable and quick to load.
Sadly all of these tools are Flash based so I’ll probably do another review in the future when more HTML5 tools are released.
I have been solving more Project Euler problems. I have now posted Python code on my Tumblr for the following:
When programming to calculate prime numbers you have a lot of options. The obvious (and slow) option is to make an array called primes and then loop up to a number, each time checking if the number in the loop (say x) can be divided by any of the primes that have already been calculated and if not add it to the array of primes. This method does work well, it is just very, very slow. I generated all the prime numbers up to 4,000,000 with a Java program running like this in just over an hour on a relatively slow computer. Using the sieve method on the same computer I was able to do it in ten seconds.
So how does sieving work? Say that you wanted to calculate all the prime numbers up to 10. You would mark 0-9 as True to state that they are prime. You would then take 2 and loop through all multiples of 2 marking them as false (not prime). This would then tell us that 4, 6 and 8 weren’t prime. We would then take 3 and mark all of its multiples as not prime (6 and 9). We could take four but we might as well check that it hasn’t been marked already so we can skip it. We don’t need to do five because clearly any multiples will be outside the array.
Here’s how we would do it in Python:
primes = [True] * max
primes = False
for i in xrange(2, int(max/2)+1):
for x in xrange(2*i, max, i):
primes[x] = False
final = 
for i in xrange(1, max):
if primes[i]: final.append(i)
Let me go through that step by step:
- Create an array where all the numbers are marked as prime
- Set 1 as not prime
- Loop through all the values in the array – we only go half way because anything above max/2 will be greater than max
- We check that the algorithm currently thinks that it is prime
- We then loop through all multiples of that number marking them as not prime
- We create a new array
- We loop through the original array checking for primes and adding them to the new array
- Return the new array
Overall sieving primes is incredibly efficient if it is done properly and is far more effective than other techniques.
If you read my post the other day you’ll know that I’ve made a start on solving Euler problems using Python. I now have solutions to the second five problems (6-10):
one = 0
two = 0
for i in range(1, 101):
one += i*i
two += i
two *= two
print str(two - one)
def is_prime(n, primes):
for i in primes:
if not n % i:
primes = [2, 3, 5, 7, 11, 13]
i = 15
if is_prime(i, primes):
if len(primes) == 10001:
i += 1
number = "731671765..."
greatest = 0
for i in range(0, 996):
if (int(number[i+0]) * int(number[i+1]) * int(number[i+2]) * int(number[i+3]) * int(number[i+4])) > greatest: greatest = int(number[i+0]) * int(number[i+1]) * int(number[i+2]) * int(number[i+3]) * int(number[i+4])
for a in range(1, 1000):
for b in range(a, 1000):
if a+b+math.sqrt((a*a)+(b*b)) == 1000:
print str(a) + "*" + str(b) + "*" + str(math.sqrt((a*a)+(b*b))) + "=" + str(a*b*math.sqrt((a*a)+(b*b)))
sieve = [True] * 2000000
def mark(sieve, x):
for i in xrange(x+x, len(sieve), x):
sieve[i] = False
for x in xrange(2, int(len(sieve) ** 0.5) + 1):
if sieve[x]: mark(sieve, x)
print sum(i for i in xrange(2, len(sieve)) if sieve[i])
You can also find solutions and explanations on my Tumblr.
I had completely forgotten that I had a Tumblr account until the other day when one of my friends reminded me that I did. I’ve been experimenting with it again so I’ve posted solutions to Euler problems 6, 7 and 8 on there. Click the image to go to my Tumblr blog (and please follow me)…