Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Project Euler - add all natural numbers below 1000
12 views
Skip to first unread message
arnuld
May 23, 2012, 7:03:09 AM5/23/12
to
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 ?
/* Add all the natural numbers below one thousand that are multiples of 3
or 5. */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
const int limit = 7;
const int multiple_A = 3;
const int multiple_B = 5;
unsigned long sum;
int i, j;
sum = 0;
for(i = 0, j = 0; (i <= limit); i = i + multiple_A, j = j + multiple_B)
{
printf("i = %d, j = %d\n", i, j);
if(j <= limit)
{
sum = sum + i + j;
}
else
{
sum = sum + i;
}
}
printf("Sum = %lu\n", sum);
return 0;
}
--
arnuld
http://LispMachine.Wordpress.com
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 ?
/* Add all the natural numbers below one thousand that are multiples of 3
or 5. */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
const int limit = 7;
const int multiple_A = 3;
const int multiple_B = 5;
unsigned long sum;
int i, j;
sum = 0;
for(i = 0, j = 0; (i <= limit); i = i + multiple_A, j = j + multiple_B)
{
printf("i = %d, j = %d\n", i, j);
if(j <= limit)
{
sum = sum + i + j;
}
else
{
sum = sum + i;
}
}
printf("Sum = %lu\n", sum);
return 0;
}
--
arnuld
http://LispMachine.Wordpress.com
Bjoern Hoehrmann
May 23, 2012, 7:30:10 AM5/23/12
to
* arnuld wrote in comp.programming:
>Question-2: Can it be improved ?
You do not say which kinds of improvements you are looking for, like if
you are using `const` the right way, whether you should have put some of
the code into a function, whether the debugging output should go to std-
err instead of stdout, whether you use unusual formatting, and so on. So
it's a bit difficult to give suitable feedback.
>/* Add all the natural numbers below one thousand that are multiples of 3
>or 5. */
>
>#include <stdio.h>
>#include <stdlib.h>
>
>int main(void)
>{
> const int limit = 7;
> const int multiple_A = 3;
> const int multiple_B = 5;
> unsigned long sum;
> int i, j;
> sum = 0;
>
> for(i = 0, j = 0; (i <= limit); i = i + multiple_A, j = j + multiple_B)
This is a bad formulation of the loop, a code reviewer would have to
think carefully about whether a check for `j` would also be needed,
especially if someone might change the constants later on.
The code does not actually seem to add all numbers 0 .. 1000 that're
integer multiplies of 3 or 5. Only goes to ten, and the sum is wrong
as you seem to forget adding 9. That might be related to the problem
with the loop condition.
--
Björn Höhrmann · mailto:bjo...@hoehrmann.de · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/
>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 ?
Not really.
>
>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 ?
you are using `const` the right way, whether you should have put some of
the code into a function, whether the debugging output should go to std-
err instead of stdout, whether you use unusual formatting, and so on. So
it's a bit difficult to give suitable feedback.
>/* Add all the natural numbers below one thousand that are multiples of 3
>or 5. */
>
>#include <stdio.h>
>#include <stdlib.h>
>
>int main(void)
>{
> const int limit = 7;
> const int multiple_A = 3;
> const int multiple_B = 5;
> unsigned long sum;
> int i, j;
> sum = 0;
>
> for(i = 0, j = 0; (i <= limit); i = i + multiple_A, j = j + multiple_B)
think carefully about whether a check for `j` would also be needed,
especially if someone might change the constants later on.
The code does not actually seem to add all numbers 0 .. 1000 that're
integer multiplies of 3 or 5. Only goes to ten, and the sum is wrong
as you seem to forget adding 9. That might be related to the problem
with the loop condition.
--
Björn Höhrmann · mailto:bjo...@hoehrmann.de · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/
H.J. Sander Bruggink
May 23, 2012, 8:11:07 AM5/23/12
to
On 05/23/2012 01:03 PM, arnuld 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
Does it? How did you test it?
> AIM: To write a program to add all natural numbers below 1000 that are
> multiples of 3 or 5.
>
> WHAT I GOT: it works
Let's test it with a limit of 16 instead of 1000. What is the correct
answer? I suspect you want it to be
3 + 5 + 6 + 9 + 10 + 12 + 15 = 60
but the output of your program is 75 because it will add 15 twice (it is
a multiple of both 3 and 5).
>
> 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 ?
>
>
>
> /* Add all the natural numbers below one thousand that are multiples of 3
> or 5. */
>
> #include<stdio.h>
> #include<stdlib.h>
>
> int main(void)
> {
> const int limit = 7;
> const int multiple_A = 3;
> const int multiple_B = 5;
> unsigned long sum;
> int i, j;
> sum = 0;
>
> for(i = 0, j = 0; (i<= limit); i = i + multiple_A, j = j + multiple_B)
> {
> printf("i = %d, j = %d\n", i, j);
> if(j<= limit)
> {
> sum = sum + i + j;
> }
> else
> {
> sum = sum + i;
> }
> }
>
> printf("Sum = %lu\n", sum);
>
> return 0;
> }
>
Sander
arnuld
May 23, 2012, 8:44:45 AM5/23/12
to
> On Wed, 23 May 2012 14:11:07 +0200, H.J. Sander Bruggink wrote:
>> arnuld wrote:
> Does it? How did you test it?
>
> Let's test it with a limit of 16 instead of 1000. What is the correct
> answer? I suspect you want it to be
>
> 3 + 5 + 6 + 9 + 10 + 12 + 15 = 60
>
> but the output of your program is 75 because it will add 15 twice (it is
> a multiple of both 3 and 5).
Down here is the corrected version.
>> arnuld wrote:
> Does it? How did you test it?
>
> Let's test it with a limit of 16 instead of 1000. What is the correct
> answer? I suspect you want it to be
>
> 3 + 5 + 6 + 9 + 10 + 12 + 15 = 60
>
> but the output of your program is 75 because it will add 15 twice (it is
> a multiple of both 3 and 5).
>> Question-2: Can it be improved ?
>
> Yes, programs that don't work can always be improved.
/* Add all the natural numbers below one thousand that are multiples of 3
or 5.
*/
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i;
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned long s = 0;
for (i = 3; i <= 1000; i += 3)
s += i;
for (i = 5; i < 1000; i += 5)
{
if(i % 3) s += i;
}
printf("%lu\n", s);
return EXIT_SUCCESS;
}
--
arnuld
http://LispMachine.Wordpress.com
Ike Naar
May 23, 2012, 9:55:11 AM5/23/12
to
On 2012-05-23, arnuld <sun...@invalid.address> wrote:
> /* Add all the natural numbers below one thousand that are multiples of 3
> or 5.
> * version 0.1
> */
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main(void)
> {
> int i;
> unsigned long s = 0;
>
> for (i = 3; i <= 1000; i += 3)
Nit: < 1000 (you want to add only numbers *below* 1000).
> /* Add all the natural numbers below one thousand that are multiples of 3
> or 5.
> * version 0.1
> */
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main(void)
> {
> int i;
> unsigned long s = 0;
>
> for (i = 3; i <= 1000; i += 3)
Here it does not matter because 1000 is not a multiple of 3,
but if you would change the limit to something that *is* a
multiple of 3, you'd get a wrong answer.
> s += i;
>
> for (i = 5; i < 1000; i += 5)
> {
> if(i % 3) s += i;
> }
>
> printf("%lu\n", s);
>
> return EXIT_SUCCESS;
> }
#include <stdio.h>
int main(void)
{
long const n = 1000;
long const n3 = (n-1) / 3;
long const n5 = (n-1) / 5;
long const n15 = (n-1) / 15;
long const sum = (3*n3*(n3+1) + 5*n5*(n5+1) - 15*n15*(n15+1)) / 2;
printf("%ld\n", sum);
return 0;
}
bob
May 23, 2012, 9:56:09 AM5/23/12
to
{
s -= i;
Jens Thoms Toerring
May 25, 2012, 5:29:06 AM5/25/12
to
arnuld <sun...@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)
> 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 ?
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 ___ j...@toerring.de
\__________________________ http://toerring.de
bob
May 25, 2012, 9:26:07 AM5/25/12
to
Jens Thoms Toerring
May 26, 2012, 5:52:45 PM5/26/12
to
bob <b...@coolfone.comze.com> wrote:
> On Friday, May 25, 2012 4:29:06 AM UTC-5, Jens Thoms Toerring wrote:
> > arnuld <sun...@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 ?
[snipped]
> On Friday, May 25, 2012 4:29:06 AM UTC-5, Jens Thoms Toerring wrote:
> > arnuld <sun...@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 ?
> > No loops involved, so computation time doesn't depend on the
> > upper limit;-)
Actually, Ike Naar posted the same solution two days earlier -
I was just too inattentive to notice it:-( And your's at least
showed the same basic idea, just using Gauss' formula had to be
added;-)
BartC
May 26, 2012, 8:52:18 PM5/26/12
to
"arnuld" <sun...@invalid.address> wrote in message
news:4fbcc3ed$0$283$1472...@news.sunsite.dk...
> 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 ?
It could be more straightforward. Working in C as you seem to, it can be
> 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 ?
just:
#include <stdio.h>
int main(void){
int i,sum=0;
for (i=1; i<1000; ++i)
if (i%3==0 || i%5==0) sum+=i;
printf("Sum = %d\n",sum);
}
Although not efficient (and the result can anyway be calculated without
loops), this at least gives the right answer by not trying anything clever.
--
Bartc
0 new messages