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.

### Like this:

Like Loading...

*Related*