Re: Project Euler - add all natural numbers below 1000

From	jt@toerring.de (Jens Thoms Toerring)
Newsgroups	comp.programming
Subject	Re: Project Euler - add all natural numbers below 1000
Date	2012-05-25 09:29 +0000
Organization	Freie Universitaet Berlin
Message-ID	<a291n2Fm87U2@mid.uni-berlin.de> (permalink)
References	<4fbcc3ed$0$283$14726298@news.sunsite.dk>

Show all headers | 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