Thread: My homework c project (help)

  1. #16

  2. #17
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    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
    954
    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; 
    }
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  4. #19
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    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,784
    It's no faster than mine :/ Is that actually fast enough for Project Euler?

  6. #21
    Registered User
    Join Date
    Dec 2017
    Posts
    954
    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.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  7. #22
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    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
    954
    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;
    }
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  9. #24
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    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,784
    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
    954
    It's nice to see the simpler solution win!
    Maybe a segmented sieve would work better?

    Anyway, it's bedtime for me.
    Later!
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  12. #27
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    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
    17
    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,784
    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
    954
    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.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

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