Tue 1 Jan 2008

#!/usr/bin/python
total = 0;
for n in range(1, 1000):
  if n%3 == 0 or n%5 == 0:
    total += n

print total

#!/usr/bin/python
f1    = 0
f2    = 1
total = 0;

while (f1+f2) < 1000000:
  tmp = f1 + f2
  if tmp%2 == 0:
    total += tmp
  f1 = f2
  f2 = tmp

print total

#!/usr/bin/python
limit = 317584931803

#function to find if a number is prime
def is_prime(n) :
  test  = 2
  while (test <= n/2):
    if(n%test == 0):
      return False
    else:
      test += 1
  return True

primes  = []  #holds prime factors
num = 2       #starting point

#loop through all possibilities until we hit the limit
while (num <= limit):

  #assume it's not a multiple of any prime numbers
  is_multiple = False
  add = 1

  #check already known primes
  for prime in primes:
    #check to see if it's a multiple of a prime number
    if(num%prime == 0):
      is_multiple = True

  #if it's not a multiple and it devides into our current limit
  if(not is_multiple and limit%num == 0):

    #actually check to see if it's prime
    if(is_prime(num)):

      #it is! don't increment our current number yet
      #until it's not a factor of our limit
      add = 0

      #add to our array, and re-calculate the new limit
      primes.append(num)
      limit = limit/num

  #incriment to the next number
  num += add

#print our results
print primes

for x in range(2, 317584931803):
  #creates array with 317584931803 variables! yikes!

6 Responses to “ Project Euler ”

Comments:

1. shollamonster says:
   January 1st, 2008 at 8:44 pm

   for problem 1, my first instinct was to only compute the numbers themselves, as in something like:

   %initialize as:
   x=3;
   y=5;

   while or for, or whatever
   x += 3;
   y += 5;

   although I guess you would need two loops since x and y would reach a million at different rates, obviously, or a single loop with a means of checking x, y to make sure they are under a million and stop adding contributions after that point. heh, as usual the idea seemed better until 5 seconds ago when I went to type some psuedocode above…

   This site looks excellent though. I am fairly good with C++…at least I was when I last used it 4 years ago, so this will be good for getting back into programming with it.

   The great thing, too, is that you can in theory do these problems over and over in different languages, which I might make a goal to work through these in C++, and then maybe start some scripting languages or something.

2. Jason says:
   January 5th, 2008 at 1:37 am

   I showed you mine for problem 3. Instead of going threw the entire loop I pulled out the factors and “reset” the loop.

   x = 10
   xnew = x
   for i in 2 to xnew
   find prime and store; first prime is 2
   x = xnew/i ;reduce by found prime
   i = 1 ; set loop back to 2

   In lisp xnew is now 5 and it will go from 2 to 5. For larger numbers it even grabs more. I now can get all primes and frequency of primes from any number in less than 0.005 seconds.

3. MrVince says:
   January 10th, 2008 at 3:31 pm

   Here’s what I did for problem 1…

   If you look at the example they gave for looking at sum of multiples of 3 or 5 that are less than 10, it boils down to

   multiples of 3 summed = 3 + 6 + 9
   multiples of 5 summed = 5

   However, I realized there was a pattern when looking at the 3’s. More specifically

   multiples of 3 summed = 3 ( 1 + 2 + 3 )
   multiples of 5 summed = 5 ( 1 )

   I realized… summation! In other words

   SUM(n) = 1 + 2 + 3 + … + n = n*(n+1)/2

   This cuts out the need for looping. All you have to do is figure out how many times 3 and 5 go into 10-1, since we are looking for values LESS than 10. In the case of 3, it goes into 10 three times, and 1 time for 5. Those “times” give me a limit as to what n should be in the SUM(n).

   So if you plug and chug…

   5 * SUM(1) + 3 * SUM(3) = 23

   However, when I did it for 1000, I tried this little number (remember 1000-1 = 999)

   5 * SUM(999/5) + 3 SUM(999/3)

   The result was incorrect! Why did it work for the example with 10 and not with 1000? I thought about it for a while and realized, I was double counting! In other words, I was adding multiples of 15 twice! 15 is the least common multiple of 3 and 5, so I was adding 15, 30, 45, etc. twice in the above formula.

   So we gotta cut out the duplicates!

   3 * sum(999/3) + 5 * sum(999/5) – 15 * sum(999/15)

   Here is my solution in Java, made a little more abstract:

   
package com.vince.euler;

   public class Problem1 {

   public static void main(String[] args) {
   if (args.length != 3) {
   System.exit(-1);
   }

   int value1 = Integer.parseInt(args[0]);
   int value2 = Integer.parseInt(args[1]);

   int max = Integer.parseInt(args[2]) - 1;
   int lcm = value1 * value2;
   int result = value1 * sum(max / value1) + value2 * sum(max / value2)
   - lcm * sum(max / lcm);

   System.out.println("result = " + result);
   }

   public static int sum(int n) {
   return n * (n + 1) / 2;
   }

   }


   No loops!

4. IrrationalPi says:
   January 13th, 2008 at 7:27 pm

   You guys got me hooked, decided to finally learn Python as well, and used sets:

   def add(x,y): return x+y

   threes = range(3, 1000, 3)
   fives = range(5,1000,5)
   both = set(threes + fives)

   print reduce(add, both)

5. Avinash says:
   April 18th, 2008 at 9:03 am

   Problem 1 is a perfect candidate for some Python goodness–if you use a list comprehension, you can elegantly one-liner the solution:

   sum([n for n in range(1000) if n % 3 == 0 or n % 5 == 0])

Leave a Reply

Trackbacks & Pingbacks:

1. Pingback from Problem 10 - More prime numbers » AaronStaves.com
   January 2nd, 2008 at 10:55 pm

   [...] a big part of all this Project Euler nonsense includes prime numbers. Problem 10, begs the ever-so-common question Find the sum of all [...]