Project Euler Solutions - Printable Version

Project Euler Solutions - Printable Version

+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: Off-Topic (https://forum.openredstone.org/forum-4.html)
+--- Forum: Programming (https://forum.openredstone.org/forum-8.html)
+--- Thread: Project Euler Solutions (/thread-2749.html)

Pages: 1 2

Project Euler Solutions - Iceglade - 03-11-2014

I've been pretty much doing continuous project euler lately. If you're not familiar with the site, it's an amazing programming website with a bunch of math/computer science problems dealing in very large numbers that you're expected to write a solution to. There are currently 462 problems (at time of writing), and counting.

Here's my github repo with my current solutions (so far I've done 50, putting me in the top 7% of users):

https://github.com/IanC162/project-euler

Enjoy :3

RE: Project Euler Solutions - Thor23 - 03-11-2014

I think I did about 10 of these, then got really hung up on finding more efficient ways to calculate primes. I still have yet to entirely write out my latest algorithm. In any case, the problems are good for improving your coding skills.

RE: Project Euler Solutions - Iceglade - 03-12-2014

Code:
a = set(range(2,n+1))

    l = round(n**0.5)

    for i in range(2,int(l+1)):

        if i in a:

            s = i**2

            while s <= n:

                if s in a:

                    a.remove(s)

                s += i

    return list(a)

This is O(sqrt n) if I'm not mistaken.

RE: Project Euler Solutions - Thor23 - 03-13-2014

Sure, sieve of Eratosthenes works, but if you're looking to calculate a large quantity of primes, it's comparatively slow. Also, small improvement I just figured out: excepting 2, you can do s += 2i to make it slightly more efficient. Smile

RE: Project Euler Solutions - Iceglade - 03-14-2014

Aha, good call.

RE: Project Euler Solutions - Thor23 - 03-17-2014

To get the thread a bit back on track, I figured I'd post the solutions to a few of the ones I did. It turns out I stopped at 7, which is (surprise surprise) the one dealing with finding prime #10001. The language is C++, and I'd post the first one but it seems I never saved it. :/

Problem #2

Code:
int main(){

    int a = 0, b = 2, c = 0;

    while(a < 4000000){

        c = c + a;

        a = 4*a + b;

        b = (a - b)/4;}

    return c;}

Problem #3

Code:
int main(){int y=0, root=0, tot=0; double z, w, v;

    vector <int> factor;

    vector <int> prime; prime.push_back(1); cin >> w;

    for(int x=2; x<sqrt(w); x++){z = x;

        while((y != prime.size()) && (root < 2) && (prime.at(y) <= sqrt(z))){

            if((x % prime.at(y)) == 0){root++;} y++;}

        if(root == 1){prime.push_back(x);} y=0; root=0;}

    for(int j=0; j<prime.size(); j++){

        v = modf(w/prime.at(j), &z);

        if(v == 0){factor.push_back(prime.at(j));}}

    return factor.at(factor.size()-1);}

Problem #4

Code:
int main(){int a=999, b=990, d, palin=0; char c[7];

    while((a >= b) && (b > 100)){d = a*b;

        if(d > palin){sprintf_s(c, 7, "%d", d);

            if((c[0] == c[5]) &&

               (c[1] == c[4]) &&

               (c[2] == c[3])){palin = d;}}

        if(a == b){a = 999; b = b - 11;}

        else{a--;}}

    return palin;}

Problem #5

Code:
int main(){int q=0, root=0, y=0; double a=30, v=1, pr, ro, z;

    vector <int> expo; expo.push_back(1);

    vector <int> prime; prime.push_back(1);

    for(int x=2; x<a; x++){z = x;

        while((y != prime.size()) && (root < 2) && (prime.at(y) <= sqrt(z))){

            if((x % prime.at(y)) == 0){root++;} y++;}

        if(root == 1){prime.push_back(x);} y=0; root=0;}

    for(int p=1; p<prime.size(); p++){

        while(q <= ceil(sqrt(a))){

            pr = prime.at(p); pr = pow(pr,q);

            if(pr > a){expo.push_back(q-1); q=0; break;}

            else{q++;}}}

    for(int r=0; r<prime.size(); r++){

        ro = prime.at(r);

        v = v * pow(ro,expo.at(r));}

    printf("%.20g\n", v); system("pause");

    return 0;}

RE: Project Euler Solutions - jxu - 05-25-2015

I have some very terse/concise answers that make nice use of Python features, if you are still around Ice
Also, for the solution you have posted Ice, I believe removing values from sets is worst case O(n), making your solution O(n^1.5). It is better in my opinion to stick with a "normal" implementation of the sieve of Eratosthenes

RE: Project Euler Solutions - Chibill - 05-25-2015

that bump!

RE: Project Euler Solutions - jxu - 06-08-2015

Well it's fun writing concise code and optimizing sometimes with 2-100x speed increases

RE: Project Euler Solutions - VoltzLive - 06-15-2015

All my solutions will be in Haskell! <3

#1

Code:
sum [x | x <- [3..999], (x `mod` 3==0)||(x `mod` 5==0)]

Code:
fib = 1 : 1 : zipWith (+) fib (tail fib)

sum [x | x <- takeWhile (<4*10^6) fib, x `mod` 2 == 0]

#3 I don't like Prime numbers...
#4

Code:
isPalindrome n = ((head n) == (last n)) && isPalindrome (tail . init n)

max [x * y| x <- [1..999], [1..999], isPalindrome (x * y)]

Code:
foldl1 lcm [1..20]

Code:
(sum (map (^2) [1..100])) - (sum [1..100])^2