Thread: My homework c project (help)

  1. #16
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665

  2. #17
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    I don't think I'm going to win any speed contests hahaha

    Cobbled together from scraps of info on the web

    Code:
    $ time ./euler_443 
    2744233049300770
    
    real    0m27.233s
    user    0m27.152s
    sys     0m0.003s

  3. #18
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    I found a C++ solution online that works. It was written by a bad programmer but paring it down yields a 34 line program.
    Code:
    #include <iostream>
    #include <vector>
    #include <cmath>
     
    typedef long long int64;
     
    template <typename T> T gcd(T x, T y) {
        for (T t; x; ) { t = x; x = y % x; y = t; }
        return y;
    }
     
    int64 find(int64 n) {
        int64 g = n * 3;
        int end = sqrt(n);
        for (int i = 1; i <= end; ++i) {
            g += gcd(g, n + i);
            if (g == (n + i) * 3) {
                n += i;
                i = 0;
            }
        }
        return n;
    }
     
    int main() {
        const int64 N = 1e15;
        int64 n = 9;
        do {
            int64 x = find(n);
            n = x * 2;
        } while (n <= N);
        std::cout << n + N << '\n';
        return 0; 
    }
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  4. #19
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    Quote Originally Posted by john.c View Post
    I found a C++ solution online that works. It was written by a bad programmer but paring it down yields a 34 line program.
    Code:
    #include <iostream>
    #include <vector>
    #include <cmath>
     
    typedef long long int64;
     
    template <typename T> T gcd(T x, T y) {
        for (T t; x; ) { t = x; x = y % x; y = t; }
        return y;
    }
     
    int64 find(int64 n) {
        int64 g = n * 3;
        int end = sqrt(n);
        for (int i = 1; i <= end; ++i) {
            g += gcd(g, n + i);
            if (g == (n + i) * 3) {
                n += i;
                i = 0;
            }
        }
        return n;
    }
     
    int main() {
        const int64 N = 1e15;
        int64 n = 9;
        do {
            int64 x = find(n);
            n = x * 2;
        } while (n <= N);
        std::cout << n + N << '\n';
        return 0; 
    }
    Where was that? (Edit: nevermind, found it)

    It's essentially the same as mine (I used C... same strategy though)

    Edit: Oh, my GCD is very different but that's not the important bit here so *shrug*.
    Last edited by Hodor; 12-12-2019 at 12:11 AM.

  5. #20
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    It's no faster than mine :/ Is that actually fast enough for Project Euler?

  6. #21
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    Quote Originally Posted by Hodor View Post
    It's no faster than mine :/ Is that actually fast enough for Project Euler?
    I don't know. They probably give you a minute, so i guess it's fast enough.
    I wish I could fathom that Mathematica solution.
    It's mostly that Quotient line I can't figure out.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  7. #22
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    Much better:

    Code:
    $ time ./euler_443 
    2744233049300770
    
    real    0m1.016s
    user    0m0.984s
    sys     0m0.029s
    Edit: Hint the primes were important after all

  8. #23
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    Something like this?
    Code:
    #include <stdio.h>
     
    typedef long long Int;
     
    Int find_lowest_prime_factor(Int x) {
        if (x % 2 == 0) return 2;
        for (Int d = 3; d * d <= x; d += 2)
            if (x % d == 0)
                return d;
        return x;
    }
     
    int main() {
        Int limit = 1e15;
        Int i1 = 20;
        for (;;) {
            Int q = 2 * i1 - 1;
            Int p = find_lowest_prime_factor(q);
            Int k = (p - 3) / 2;
            Int i2 = i1 + k + 1;
            if (i2 > limit)
                break;
            i1 = i2;
        }
        
        printf("%lld\n", 3 * i1 + (Int)(1e15 - i1));
        return 0;
    }
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  9. #24
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    Quote Originally Posted by john.c View Post
    Something like this?
    Yes, exactly that but I used a sieve. I like yours better

    Yours is twice as fast as well. I just ran mine through cachegrind and I'm wasting a whole bunch of time creating the sieve (oops)
    Last edited by Hodor; 12-12-2019 at 01:07 AM.

  10. #25
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    I hope the OP learned something from their homework. I guess at least a process of problem solving has been documented even if the intermediate steps towards arriving at a fast solution are somewhat vague or missing completely (mostly because there is no way I'm going to take a photo of my piece of paper with scribbles all over it).

  11. #26
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    It's nice to see the simpler solution win!
    Maybe a segmented sieve would work better?

    Anyway, it's bedtime for me.
    Later!
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  12. #27
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    Quote Originally Posted by john.c View Post
    It's nice to see the simpler solution win!
    Maybe a segmented sieve would work better?

    Anyway, it's bedtime for me.
    Later!
    sleep well

  13. #28
    Registered User
    Join Date
    Dec 2019
    Posts
    9
    Quote Originally Posted by john.c View Post
    Something like this?
    Code:
    #include <stdio.h>
     
    typedef long long Int;
     
    Int find_lowest_prime_factor(Int x) {
        if (x % 2 == 0) return 2;
        for (Int d = 3; d * d <= x; d += 2)
            if (x % d == 0)
                return d;
        return x;
    }
     
    int main() {
        Int limit = 1e15;
        Int i1 = 20;
        for (;;) {
            Int q = 2 * i1 - 1;
            Int p = find_lowest_prime_factor(q);
            Int k = (p - 3) / 2;
            Int i2 = i1 + k + 1;
            if (i2 > limit)
                break;
            i1 = i2;
        }
        
        printf("%lld\n", 3 * i1 + (Int)(1e15 - i1));
        return 0;
    }
    Thank for your solving but actually i donít understand exactly. Can you share your algorithm with us? This homework is very imptortant to me. Thanks again.

  14. #29
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,665
    Quote Originally Posted by muhammetekurt View Post
    Thank for your solving but actually i don’t understand exactly. Can you share your algorithm with us? This homework is very imptortant to me. Thanks again.
    Did you try printing out lists of numbers like john.c suggested? I ended up with a fourth list as well and looked at the numbers, made some observations, graphed them (this helped) and scribbled on paper. Doing this a pattern does emerge. Edit: did you read where I said that the primes are important? (and 9 is as well)
    I can explain it, but you might want to try it yourself first.

    What's this homework for?
    Last edited by Hodor; 12-12-2019 at 04:41 PM.

  15. #30
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    I vote to not explain it to him. If he can't figure it out from what's been given so far then that's too bad.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need Help With C++ Console Homework Project
    By Sikkirigi in forum C++ Programming
    Replies: 14
    Last Post: 04-07-2016, 10:54 AM
  2. Replies: 4
    Last Post: 08-02-2013, 06:45 PM
  3. Replies: 5
    Last Post: 02-23-2013, 03:37 PM
  4. This Is Not Homework/ A Project
    By joebenjamin in forum C Programming
    Replies: 2
    Last Post: 09-24-2007, 08:42 PM
  5. Homework project(need help)
    By kantze in forum C++ Programming
    Replies: 8
    Last Post: 12-15-2006, 10:41 AM

Tags for this Thread