Project Euler #3: Find largest prime factor

Approach: Keep evenly dividing the upper limit by numbers which are smaller than its square root. When further such division is impossible the result is the largest prime number which is a factor of the upper limit.

>>> from math import sqrt
>>> from math import floor
>>> upperLimit = 600851475143
>>> i = 2
>>> stoppingPoint = floor(sqrt(upperLimit))
>>> while (i < stoppingPoint):
... if (upperLimit % i == 0):
... upperLimit /= i
... stoppingPoint = floor(sqrt(upperLimit))
... else:
... i += 1
...
>>> upperLimit
6857L
>>>

Euler Problem #2: Fibonacci Numbers

fibonacci() is from Diving Into Python by Mark Pilgrim

>>> def fibonacci():
... a,b = 0,1
... while a <= 4000000:
... yield a
... a,b = b, a + b
...
>>> total = 0
>>> for n in fibonacci():
... if n%2 == 0:
... total += n
...
>>> print total
4613732

First Problem: Find sum of all factors of 3 and 5 that are less than 1000

Solved using Python 2.4.4.

Approach:

(1) Take the average of the non-negative multiples of 3 which are less than or equal to 999.
(2) Multiply that by the count of the non-negative multiples of three which are less than or equal to 999
(3) Do the same for multiples of 5
(4) Do the same for multiples of (3 * 5 = 15)
(5) Add (2) and (3) and subtract (4) so as to avoid double-counting numbers which are multiples of both 3 and 5.

>>> def sum_of_factor(n):
... number_of_ints = 999//n + 1
... count_of_positive_ints = 999//n
... largest_positive_int = count_of_positive_ints * n
... average_int = (0 + largest_positive_int)/2.
... total_ints = (count_of_positive_ints + 1) * average_int
... return total_ints
...
>>> sum_of_factor(3)
166833.0
>>> sum_of_factor(5)
99500.0
>>> sum_of_factor(15)
33165.0
>>> sum_of_factor(3) + sum_of_factor(5) - sum_of_factor(15)
233168.0