Warning, this post contains code for Euler problem 5. Try to solve it youself without looking at anyones code. Its alot more satisfying if you do it yourself.

Hello, just found an interesting website called project euler. I managed to get to problem 5 without a too many problems. Anyways I'm at the debugging stage, and I must say that I've never seen anything like this.:-O

``````/* Euler problem 5:
2520 is the smallest number that can be divided by each of the numbers from 1
to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers
from 1 to 20? */

#include <stdio.h>

int ldivisibleby(int max);
int isdivisible(int max, int number);

int main() {
printf("%d\n", isdivisible(10, 360)); /* For debugging */
printf("The smallest number that is evenly divisible by all the numbers from "
"1 to 10 is: %d\n", ldivisibleby(10));

return 0;
}

int ldivisibleby(int max) {
/* This function returns the lowest number divisible by 1 to 'max'. Max must be
at least 2. It works by increacing the test number by max, and checking if
its divisible by the numbers 1 to 'max'. If it isnt, increase test and try
again. */

int curnum = max;

while(1) {
if(isdivisible(max, curnum)) {
if(curnum == 360) /* For debugging */
printf("Debug\n"); /* For debugging */
return curnum; }
curnum += max;
}
}

int isdivisible(int max, int number) {
/* This function returns 1 if the number is divisible by every number between 1
and 'max'. It only tests against 2 and odd numbers above 2 to save time
(all numbers are divisible by 1, and if the number is divisible by 2, its
divisible by all even numbers.) */

int count = 3;

if(number % 2 != 0)
return 0;

while(count < max) {
if(number % count != 0)
return 0;
count += 2;
}
return 1;
}``````

And the output is:

``````0
The smallest number that is evenly divisible by all the numbers from 1 to 10 is: 630``````

First of all, 630 is divisible by 7. According to the 0 at the top, 630 is not the answer. Becouse "Debug" did not appear under the 0, 630 should have never been returned, but it is anyway. I'm using gcc v4.2. Any explinations. (P.S. I don't want people to point out bug's that arnt related to this one. I'll sqwish those bugs as soon as it starts telling the truth.)
Thanks alot to anyone who can help me. :)

3
Contributors
6
Replies
7
Views
9 Years
Discussion Span
Last Post by iamthwee

Ahem, 350 is divisable by 7 with no remainder. 360 is not!

Also only doing divisor by 2 is not valid because a number may be divisable by 2 but not by another even number.

How about 198 % 2 okay, then 198 % 4 ?

Thanks =)

There's actually a simpler solution to find the smallest number divisable between 1 and N.

Do a running total with dividends!

1 2 3 4 5 6 7 8 9 10
2 x 3 x 2 x 5 x 7 x 2 x 3 = 2520

If Divisor has a remainder of previous accrued dividends then find the find the divident that needs repeating!

Much fewer computing cycles!

Thanks for the reply's. Did I say 360? I ment 630. Yes you right about the dividing by 2 thing, I was thinking of primes for some reason (all primes above 2 are odd). Those are all bugs. I'm just wondering about my origonal question, why is it returning 630 even though everything the debug is saying its not?

Aha! The reason is I tested for 360 instead of 630 in my debug's (guess im dyslexic ;) ) And the reason why my isdivisible() function does not work is the divisible by two thing (thanks wildgoose).

How many times have I heard, 'It must be the compiler that's wrong.'

Another keyboard to chair interface problem no doubt!