Path: csiph.com!usenet.pasdenom.info!news.albasani.net!fu-berlin.de!uni-berlin.de!not-for-mail
From: jt@toerring.de (Jens Thoms Toerring)
Newsgroups: comp.programming
Subject: Re: Project Euler - add all natural numbers below 1000
Date: 25 May 2012 09:29:06 GMT
Organization: Freie Universitaet Berlin
Lines: 43
Message-ID: <a291n2Fm87U2@mid.uni-berlin.de>
References: <4fbcc3ed$0$283$14726298@news.sunsite.dk>
X-Trace: news.uni-berlin.de dJ6Ptqur2lCtFeOLsM1LBQrK4+1e9xAXn9GmcFLhaaWJ+zHzH1YknjRgDGcL1c
X-Orig-Path: not-for-mail
User-Agent: tin/1.9.3-20080506 ("Dalintober") (UNIX) (Linux/2.6.30-1-amd64 (x86_64))
Xref: csiph.com comp.programming:1619

arnuld <sunrise@invalid.address> wrote:
> AIM: To write a program to add all natural numbers below 1000 that are 
> multiples of 3 or 5.

> WHAT I GOT:  it works

> Question-1:  Look at the for loop, instead of looping for 1000 times and 
> checking the value inside, I am simply looping it 1000/3 = 333 times. Ist 
> that impressive ?

> Question-2: Can it be improved ?

Yes, quite a lot. You now use O(n) but it can be done using O(0)
operations. Just integer divide the highest number you wnt to
include (i.e. 999 in you case) by 3 and add all integers up to
the result (333 in your case) using the well known formula (de-
veloped by Gauss more than 200 years ago when he was still a
schoolboy):

  s = n * ( n + 1 ) / 2

Multiply the result by 3. You end up with

  sum3 = 3 * ( 333 * 334 ) / 2

Do the same for 5

  sum5 = 5 * ( 199 * 200 ) / 2

Now do it again for 15 (the product of 3 and 5)

  sum15 = 15 * ( 66 * 67 ) / 2

The total sum you are looking for is then

  sum = sum3 + sum5 - sum15

No loops involved, so computation time doesn't depend on the
upper limit;-)
                         Regards, Jens
-- 
  \   Jens Thoms Toerring  ___      jt@toerring.de
   \__________________________      http://toerring.de