Thread: My homework c project (help)

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; 
}

Originally Posted by john.c

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*.

Originally Posted by Hodor

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.

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;
}

Originally Posted by john.c

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)

It's nice to see the simpler solution win!
Maybe a segmented sieve would work better?

Anyway, it's bedtime for me.
Later!

Originally Posted by muhammetekurt

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?

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.