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)

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

RE: Project Euler Solutions - Legofreak - 07-06-2015

I tried this for the first time today... I don't know any programming languages so I used scratch...

problem #1

I have a feeling I won't be solving any more of these...

edit:

took me long enough to figure out how to determine if something is even or odd...
problem #2

and I figured out problem #5 on a calculator

RE: Project Euler Solutions - jxu - 07-10-2015

(07-06-2015, 09:25 PM)Legofreak Wrote: I used scratch

jesus it's probably better to use a calculator than this (i'm sure the first 20 are possible with only calculator)

RE: Project Euler Solutions - jxu - 10-18-2015

I can't stop doing these problems

They're just too interesting, too intriguing

RE: Project Euler Solutions - Hastumer - 11-10-2015

So I found myself installing Python and Sublime Text again to revive my Project Euler account. Project one solution:

Code:
x = 1

sol = 0

while x < 1000:

    m = x % 3

    if m == 0:

        sol += x

    else:

        m = x % 5

        if m == 0:

            sol += x

    x += 1

print(sol)

Pretty tiny for me actually! Only 12 lines of code! I bet you can do it with less, but that's actually fine for me!

RE: Project Euler Solutions - Hastumer - 11-10-2015

And I made the second one first try!

Code:
x = 1

y = 1

s = 0

while x + y < 4000000 and x + y * 2 < 4000000:

    x += y

    if x % 2 == 0:

        s += x

    y += x

    if y % 2 == 0:

        s += y

if x + y < 4000000:

    x += y

    if x % 2 == 0:

        s += x

    print(s)

else:

    print(s)

RE: Project Euler Solutions - VoltzLive - 11-12-2015

#1 in Python

Code:
sum([ x for x in range 1000 if (x % 3==0) | (x % 5 == 0)])

edit: even smaller

RE: Project Euler Solutions - jxu - 01-24-2016

Reduce is unnecessary (and deprecated in Python 3). sum() does the trick

RE: Project Euler Solutions - Chibill - 01-25-2016

Dang you Snh1