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());
}
385 = 2640.
99.
