Solution to Project Euler 2


Time for another solution of the Project Euler. Problem 2 is not that difficult either, but it will require more computing power. Here’s the description:

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Basically we need a function to generate Fibonacci numbers, generate all numbers below 4 million, for each one checking whether it’s even or not. In case it’s even we add it to the sum.

The only pitfall is to use a recursive version of Fibonacci, which is exponential in complexity and would be very inefficient. I used an iterative one, but the best solution would be one with memoization of the results in a separate table.

Below my C code:

#include <stdio.h>

int fib(int n){
  int i;
  int f1=1;
  int f2=1;
  if (n==0 || n==1)
    return f1;
  else{
      for (i=1;i<n;i++){
      f1=f1+f2;
      f2=f1-f2;
      }
      return f1;
  }
}

int main(){
    int i,x;
    int sum=0;
    for (i=1;i<1000;i++){
  x=fib(i);
  if (x>4000000)
    break;
  if (x%2==0)
    sum+=x;
    }

    printf("%dn",sum);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *