Algorithm Runtime Optimisation

Well now, it turns out that there many methods of calculating primes.

Algorithm 1: The obvious algorithm would be to test any given number, p, by all preceding numbers, 2..(p-1).  However, this becomes exponentially slower as p increases.

Algorithm 2: So one might think, that there is a natural mirror plane in the factors of p, such that we can disregard the complimentary factors and only test the values, 2 .. (p // 2) . Though again, for sufficiently large values of p this will be expensive.

Algorithm 3: This is the latest version I have posted, which only tests the values, 2 .. sqrt(p).

Algorithm 4: There is another definition of prime. A number, p, is prime if it can not be evenly divided by all preceding primes. So as we go, we will build a list of known prime numbers, and we can test only against this list. This seemed like a great solution to me, so I thought I would compare the runtime of Algorithm 4 vs. Algorithm 3. This is what I got:


Figure 1: Run time of Algorithm 3 (BLUE) and Algorithm 4 (GREEN)

Intuitively, I felt that Algorithm 4, which only tested against other prime numbers would have the advantage. however we can see in Fig 1 that Algorithm 4 grows exponentially (O(n^2)) as p increases. Compare this to logarithmic growth (O(logn)) of Algorithm 3 (logarithmic scal not obvious next to Algorithm 4) and we can see that Algorithm 3 wins hands down.

So when it comes time to do prime-related challenges on Project Euler, I will be using the lightening fast Algorithm 3.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s