Re: Project Euler - add all natural numbers below 1000

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> (permalink)
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

Show key headers only | View raw

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

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Project Euler - add all natural numbers below 1000 arnuld <sunrise@invalid.address> - 2012-05-23 11:03 +0000
  Re: Project Euler - add all natural numbers below 1000 Bjoern Hoehrmann <bjoern@hoehrmann.de> - 2012-05-23 13:30 +0200
  Re: Project Euler - add all natural numbers below 1000 "H.J. Sander Bruggink" <sander.bruggink@uni-due.de> - 2012-05-23 14:11 +0200
    Re: Project Euler - add all natural numbers below 1000 arnuld <sunrise@invalid.address> - 2012-05-23 12:44 +0000
      Re: Project Euler - add all natural numbers below 1000 Ike Naar <ike@sverige.freeshell.org> - 2012-05-23 13:55 +0000
      Re: Project Euler - add all natural numbers below 1000 bob <bob@coolfone.comze.com> - 2012-05-23 06:56 -0700
  Re: Project Euler - add all natural numbers below 1000 jt@toerring.de (Jens Thoms Toerring) - 2012-05-25 09:29 +0000
    Re: Project Euler - add all natural numbers below 1000 bob <bob@coolfone.comze.com> - 2012-05-25 06:26 -0700
      Re: Project Euler - add all natural numbers below 1000 jt@toerring.de (Jens Thoms Toerring) - 2012-05-26 21:52 +0000
  Re: Project Euler - add all natural numbers below 1000 "BartC" <bc@freeuk.com> - 2012-05-27 01:52 +0100

csiph-web