Thread: project Euler problem 5 solution

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    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

  2. #2
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Long story short - Recursion is not linear

  3. #3
    Registered User
    Join Date
    May 2019
    Posts
    213
    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.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    639
    Quote Originally Posted by Click_here View Post
    Long story short - Recursion is not linear
    Well... his problem is not the recursion per se, but how he's testing the range...

  5. #5
    Registered User
    Join Date
    Feb 2019
    Posts
    639
    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

  6. #6
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  7. #7
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    701
    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];
    }

  8. #8
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  9. #9
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  10. #10
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    701
    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

  11. #11
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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?

  12. #12
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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.

  13. #13
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    it takes my second soloution 58 seconds to work out n = 28

  14. #14
    Registered User
    Join Date
    Feb 2019
    Posts
    639
    @cristop. Hummmm... I didn't thought about using a lookup table (makes sense, since there are only 42 possible values for the upper range before a unsigned long long overflows!). My implementation uses the fact that the "least common multiple" can be calculates as:

    lcm(a,b) = (a * b) / gcd(a, b);

    Since we are checking for a range of values:

    n = lcm(2, lcm(3, lcm(4, ... lcm(n-1, n)...)));

    Using a binary implementation for gcd() I got a 2 ms runtime for max=42 (43 overflows).
    Last edited by flp1969; 06-03-2019 at 01:59 PM.

  15. #15
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    whats gcd??

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help!! Problem 3 of Project Euler
    By i++ in forum C Programming
    Replies: 8
    Last Post: 08-15-2013, 06:59 PM
  2. Project Euler Problem 2 Solution
    By i++ in forum C Programming
    Replies: 1
    Last Post: 08-10-2013, 09:24 AM
  3. Project Euler problem
    By nimitzhunter in forum C++ Programming
    Replies: 6
    Last Post: 04-15-2012, 09:00 PM
  4. Project Euler Problem 8
    By deadrabbit in forum C Programming
    Replies: 2
    Last Post: 10-06-2011, 10:56 PM
  5. Project Euler problem 3
    By SELFMADE in forum C Programming
    Replies: 7
    Last Post: 09-16-2009, 03:33 AM

Tags for this Thread