Project Euler Solutions

[Iceglade]

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

[Thor23]

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.

[Iceglade]

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.

[Thor23]

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.

[Iceglade]

Aha, good call.

[Thor23]

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

[jxu]

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

[Chibill]

that bump!

[jxu]

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

[VoltzLive]

All my solutions will be in Haskell! <3 

#1

Code:

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

#2

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)]

#5

Code:

foldl1 lcm [1..20]

#6

Code:

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

[Legofreak]

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

[jxu]

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)

[jxu]

I can't stop doing these problems

They're just too interesting, too intriguing

[Hastumer]

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!

[Hastumer]

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)

[VoltzLive]

#1 in Python

Code:

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

edit: even smaller

[jxu]

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

[Chibill]

Dang you Snh1