Project Euler Problems #1 and #2

I've been mighty bored this summer since I decided to take it off from school and drop my summer class (BIG MISTAKE), so I decided to delve into the Project Euler problems (http://projecteuler.net/). I only finished #1 and #2 so far and am working on #3. I work full-time so I still don't have much time to dedicate to it. I don't think this will get read much, but there is maybe someone on here who can potentially benefit from reading these solutions.

 

Problem #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.

 

This one is quite easy. You just need to take all the multiples of 3 and 5 up to 1000 and add them all together. This can be done on paper with a pencil using sigma notation, but we're using a computational device! Why do all the hard work of calculating in your head or busting out a calculator when you can just create a for loop to do it for you.

 

There are two ways (the first two ways that came to my mind anyway) to gather up all the multiples of 3 and 5. Either use multiplication or modular arithmetic. Modular arithmetic gets me hard so I decided to use that method.

 

int result = 0;

for(int i = 0; i < 1000; i++) {
           
            if (i % 3 == 0 || i % 5 == 0){
                result += i;
               
            }

  }

(Note: I forget curly braces in my initial code and just discovered for-loops run without them; mind = blown)

 

Basically, we're taking out all the i's that have a remainder of 0 when divided by 3 or 5. Example: 3 % 3 = 0, 9 % 3 = 0, 45 % 5 = 0, etc. Take out all those natural numbers that have a remainder of 0 when divided by 3 or 5, add them together, and voila! You have your answer. Quite simply.

 

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

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

 

 

This problem uses a lot of the same principles used in problem 1, you're just looking for a different result using a different set of numbers. Also, I cheated. Sorry. I know I should use all of my own code to solve these, but it's tempting to look up quick solutions to problems that are tedious and have been done hundreds of times. A programmer should be talented, but also resourceful! It saves precious time. Knowing what you need and how to implement it is just as important (feel free to disagree with me!).

 

The part I cheated on was the fibonacci sequence. That is all. I looked up a quick algortihm to produce the number at a given term.

 

public static int fib(int n) {
        int prev1=0, prev2=1;
        for(int i=0; i<n; i++) {
            int savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1 + prev2;
        }
        return prev1;
    }

 

 

so fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, and so on.

 

With this working, all we need to do is create a for-loop to run through all the terms in the sequence that do not exceed four million. To get the even valued terms we again use the modulus operator to check if it's an even term and add it to our 'result' variable.

 

for(int i = 1; fib(i) < 4000000; i++){
            if (fib(i) % 2 == 0) {
                result += fib(i);
            }
        }

(Note: I actually didn't know you could use a method in the condition part of the for-loop. Not all that important, but I thought it was cool)

 

 

And that's that! Quite simple really.

 

I hadn't programmed since classes ended but this was really fun. I always loved solving little problems like these and hated working on giant, 100+ lines of code. Don't know why. Hopefully working on Problem #3, which is considerably tougher, tonight when I get home from work. It has to do with large integers and their prime factorization - an important topic in cryptography! What's even more lovely about these problems is their links with number theory, the most beautiful subject in mathematics.

 

IDE used: eclipse.