Project Euler #3: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I started off by recycling the code from PE-10. To find the largest prime factor I'm going to find ALL the prime factors. By finding them in increasing order, I'm guaranteed that the last one I find will be the largest prime factor (side note: this also works if the inputted number is a prime number since the factors are 1 and itself).

I begin by setting the limit to the inputted number and starting at 5 and repeating my earlier method to find prime numbers in increasing order (sieving on 2 and 3, then using the idea that the smallest prime factor must be less than or equal to the square root of the number being tested if it's NOT a prime number). For every prime number I test if it's a factor of the inputted number. If it isn't then I store it in my prime number vector and move on. However, if it is then I set the new limit to be the old limit divided by this prime factor. Then I repeat the process. I continue until I reach the limit.

This works only because I'm finding the prime factors in order. Once we find one, we know the next one must be greater or equal to the one we just found. Thus I can continue on in my for-loop, only having to retest the most recent prime number (e.g. 8 is 2x2x2) before moving on. I like this solution because the amount of numbers we test is quite low so it scales really well.

For example, this problem asked for the prime factors of 600851475143. The prime factors are:

1. 71, new limit is 8462696833
2. 839, new limit is 10086647
3. 1471, new limit is 6857
4. 6857, new limit is 6857 (since they're equal)

Once the latest prime factor equals the limit we know we're done! So we only had to test roughly ~1142 numbers (6857 / 6 since we sieved). I'm not sure if the runtime I measured using is accurate, but it's returning 502 microseconds. I didn't bother making a naive version for this one since I was lazy.

The code can be found here.

Project Euler #10: Summation of primes

This post is copied from another blog I run. I'll be shutting that blog down shortly and all future posts of that kind will go on this blog. These are solutions to various programming brain teasers. Optimizing your solution is the real challenge.

The problem reads as follows:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Right from the start I can think of two methods:

1. Using a similar solution as for PE-7 but adding the primes instead of storing them
2. Sieve of Eratosthenes

I opted for the first method since I'm lazy. With minimal modifications, I get 173518 microseconds as my runtime. I was curious about the second method, so I copied and modified a solution found in the problem discussion thread. You can find that one under sieve.cpp. It has a runtime of 221631 microseconds. That's still pretty good.

The third way I can think of is to combine the first two methods. As with PE-7, automatically exclude all multiples of 2 and 3 for a 2/3 reduction in numbers considered. Then find all the primes below the square root of 2 million (so anything below and including 1415) and sieve on the remaining 1/3 with those prime numbers. Could result in a nice speedup over the first method. As usual, another thing you could do is to remove the use of the modulus operand - it's expensive.

The code can be found here