a blog about nerdy things

Today’s daily funny comes to you thanks to eclipse and the android sdk.

As a way to get reacquainted with c++, I’m revisiting all my PE problems.  Here’s the code for #1.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

#include <iostream>

int main(int argc, char* argv[])
{
    int iMax = 1000;
    int iSum = 0;
    int iMultiplesOf[2] = { 3, 5 };
    for each (int iNum in iMultiplesOf)
    {
        for (int i = 0; i * iNum < iMax; i++)
        {
            iSum += i * iNum;
        }
    }
    std::cout << iSum << std::endl;
    system("PAUSE");
    return 0;
}

The problem:

Public Sub Difference()
    Dim iStart, iEnd, iSumOfSquares, iSquareOfSum As Integer
    iStart = 1
    iEnd = 100
    iSumOfSquares = 0
    iSquareOfSum = 0

    For iCounter As Integer = iStart To iEnd
        iSumOfSquares = iSumOfSquares + iCounter ^ 2
        iSquareOfSum = iSquareOfSum + iCounter
    Next

    Response.Write(iSquareOfSum ^ 2 - iSumOfSquares)
End Sub

projecteuler.net is one of my new favorite addictions.  i’ll be periodically posting my solutions to the problems on this site to keep track of my algorithms.  this is problem #2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

and this is my brute force solution done in asp.net:

protected void Page_Load(object sender, EventArgs e)
{
	long prevFib = 0;
	long currFib = 1;
	long sum = 0;
	while (currFib < 4000000)
	{
		if (currFib % 2 == 0)
		{
			sum += currFib;
		}
		currFib += prevFib;
		prevFib = currFib - prevFib;
	}
	Response.Write(sum.ToString());
}

this is problem #3:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

and this is my solution which started off brute force but reduces the target number every time it finds a new prime factor causing a drastic reduction in processing time:

protected void Page_Load(object sender, EventArgs e)
{
	long target = 600851475143;
	for (long counter = 2; counter < target; counter++)
	{
		// is counter a factor?
		if (target % counter == 0)
		{
			// find out if counter is prime
			bool print = true;
			for (long i = 2; i < counter; i++)
			{
				// if counter isn't prime,
				// cut out of for-loop and don't print
				if (counter % i == 0)
				{
					i = counter;
					print = false;
				}
			}
			if (print)
			{
				Response.Write(counter.ToString() + "<br/>");
				// counter is a prime factor.  let's divide target
				// by counter to get a smaller target to work with.
				target = target / counter;
			}
		}
	}
	Response.Write(target.ToString());
}