Thread: project Euler problem 5 solution

problem 5 states that the smallest number that is devisable by all the integers between 1 and 10 is 2520 and asks the question what is the smallest number that is devisable by all the integers between 1 and 20.

here is my soloution

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 500000000

int divide(long int num, int divisor);

int main()
{
    int result, max_divisor;
    long int num_divide;
    clock_t start, finish;

    printf("Please enter the max number to divide by: ");
    scanf(" %d", &max_divisor);

    start = clock();

    for (num_divide = max_divisor; num_divide < MAX_NUM; num_divide += max_divisor)
    {
        if((result = divide(num_divide, max_divisor)))
        {
            break;
        }
    }

    finish = clock();

    if (result == -1)
    {
        printf("\nnaughty naughty you entered zero you cant divide by zero!\n");
    }
    else if (result == 0)
    {
        printf("\nthere is no number between 1 and %d that can be divided by all the integers 1 to %d\n", MAX_NUM, max_divisor);
    }
    else
    {
        printf("\nthe smallest number that can be divided by all the integers 1 to %d is %ld\n", max_divisor, num_divide);
    }

    printf("\ntime taken is %.6f seconds\n", (double)(finish - start) / (double)CLOCKS_PER_SEC);
    return 0;
}

int divide(long int num, int divisor)
{
    // sanity checks

    if (num == 0)
    {
        return - 1;
    }

    if (num % divisor != 0)
    {
        return 0;
    }
    if (divisor == 2 && num % divisor == 0)
    {
        return 1;
    }
    return divide(num, divisor - 1);
}

to answer the above question the user obviously has to enter 20 (answer is 232,792,560)
however i decided to calculate the time taken to work it out. and here comes the surprise while i do get slightly different results for each time i enter the same number (1000ths of a second) the time taken isn't linear for example it takes longer to compute max_devisor = 19 than max_devisor = 22 by roughly 0.04 seconds. why?
coop

Long story short - Recursion is not linear

I've seen this code elsewhere, and I must ask, is recursion required?

Without recursion this finds the answer in less that 3 seconds in debug mode.

With recursion, I don't know....I'm not that patient

As to why 0.04 seconds....from one run to the next you'll get wild variations in time because the OS is busy doing things you're not aware of or can account for. You must run several tests and use simple statistical methods to smooth out the noise in the samples.

That said, your routine (correctly) excludes failure quickly, as you probably know. This means the recursion is not as deep if an early test (like 22, 21) fails. When testing 20 or 19, it may be that a larger volume of test numbers have a few of those that are valid divisors (meaning it bothers to recurse deeper, going BACKWARDS). The pattern of which numbers reject quickly (like the first or second test) will differ when started at 22 vs 21 vs 20.

Originally Posted by Click_here

Long story short - Recursion is not linear

Well... his problem is not the recursion per se, but how he's testing the range...

What if I tell you that there are an algorithm to calculate this in 2 ms for any range between 1..42 (greater ranges must use multi-precision arithmetic!)...

Code:

$ time ./rmult <<< 42
219060189739591200 divisible by all values from the range [1..42].

real    0m0,002s
user    0m0,002s
sys    0m0,000s

i wasn't given an algorithm i was simply given the fact that 2520 is the smallest number that is devisable by 1 through 10, and asked to find what the smallest number devisable by 1 to 20 was. on another post someone suggested trying to figure out what numbers were needed as test numbers and multiply them together which i had thought of but couldn't decide on which numbers to rule out so this was my effot that obviously is ineficent but arrives at what i assume is the correct answer.

what i didnt understand is as 19 20 21 and 22 are all the same number why it took longer to work out n = 19 than to work out n = 22

Nice. My solution to this problem can go up to 46 before the result overflows (using unsigned long long):

Code:

$ time ./euler-problem-5 <<< 46
9419588158802421600

real    0m0.001s
user    0m0.001s
sys     0m0.000s

Of course, the fastest solution is one that returns the value from a lookup table:

Code:

// assumes n is between 1 and 20, inclusive
unsigned long long problem5(int n)
{
    static const unsigned long long results[20] = {
                1,
                2,
                6,
               12,
               60,
               60,
              420,
              840,
             2520,
             2520,
            27720,
            27720,
           360360,
           360360,
           360360,
           720720,
         12252240,
         12252240,
        232792560,
        232792560,
    };
    return results[n-1];
}

i have had another go but still not as quick as you guys (ignore the while loop its only there so i can get an average time to compare with my other effot.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int num_to_divide, devisor = 20, soloution_found = 0, x = 50;
    double total_time;
    clock_t start, finish;

    start = clock();

    while (x)
    {
        for (num_to_divide = devisor; num_to_divide < 3000000000; num_to_divide += devisor)
        {
            for (devisor = 20; devisor >= 2; devisor--)
            {
                if (num_to_divide % devisor != 0)
                {
                    devisor = 20;
                    break;
                }
                if (devisor == 2 && num_to_divide % devisor == 0)
                {
                    soloution_found = 1;
                    break;
                }
            }
            if (soloution_found)
            {
                break;
            }
        }
        x--;
        devisor = 20;
        soloution_found = 0;
    }

    finish = clock();

    if (num_to_divide >= 3000000000)
    {
        printf("there is no number upto 3000000000 that is divisable by the numbers 1 to %d\n", devisor);
    }
    else
    {
        printf("%d is the smallest number that is divisable by the numbers 1 to %d\n", num_to_divide, devisor);
    }

    total_time = (double)(finish - start) / (double)CLOCKS_PER_SEC;
    printf("\ntotal time taken for 50 soloutions is %.6f seconds\n",total_time);
    printf("average time taken for 1 soloution is %.6f", total_time / 50);
    return 0;
}

coop

what answer do people get for n = 23 i have a limit of 9999999999999999999 19 9's and it still says it cant find it

I get 5354228880.

5354228880/1=5354228880
5354228880/2=2677114440
5354228880/3=1784742960
5354228880/4=1338557220
5354228880/5=1070845776
5354228880/6=892371480
5354228880/7=764889840
5354228880/8=669278610
5354228880/9=594914320
5354228880/10=535422888
5354228880/11=486748080
5354228880/12=446185740
5354228880/13=411863760
5354228880/14=382444920
5354228880/15=356948592
5354228880/16=334639305
5354228880/17=314954640
5354228880/18=297457160
5354228880/19=281801520
5354228880/20=267711444
5354228880/21=254963280
5354228880/22=243374040
5354228880/23=232792560

ok whats wrong with the first for loop then if i have the limit set to 9999999999 why does it say it cant be found?

scratch that it was finding the soloution but the if statement at the end was throwing me off because i forgot to update it duh.

it takes my second soloution 58 seconds to work out n = 28

whats gcd??