Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Jach
Posts: 167
Joined: Sat May 05, 2007 8:38 pm UTC
Contact:

Project Euler

Postby Jach » Sat May 12, 2007 5:43 am UTC

Has anyone here done much with Project Euler? There's some really neat stuff you can waste your time with on there, and after you complete a problem you open up a forum topic on that problem and can see other implementations, hopefully learning more about your language or another language and about more efficient algorithms than yours.

By the way, 18% genius! >.> I secretly hope someone here isn't 100% genius... But I wouldn't doubt it.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Postby Torn Apart By Dingos » Sat May 12, 2007 1:33 pm UTC

I was 100% genius up until about August last year, when I tired of Project Euler after the umpteenth problem about pythagorean triplets. Most of the problems were too easy (brute force in C++ was usually sufficient).

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Postby musicinmybrain » Sun May 13, 2007 3:31 am UTC

Yeah, Project Euler is a lot of fun. I'm at 49% in Python. I still sit down and do a problem now and then; it's kind of relaxing, and a nice brain exercise.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

User avatar
Aglet
Posts: 364
Joined: Tue Mar 13, 2007 12:26 am UTC

Postby Aglet » Sun May 13, 2007 4:27 am UTC

Well, since I'm away from my own computer and am without any programming tools besides Notepad, I figured I couldn't start these challenges until I got home. Or couldn't I?

I wrote all of my Python code in Notepad, then uploaded it onto the Anarchy Golf server, which always shows the output of your program whether it solves the challenges or not, and has an amazing number of programming languages supported, making it an ad hoc interpreter.

That was probably one of the cooler things I've ever done on the Internet.
Image

User avatar
adlaiff6
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?
Contact:

Postby adlaiff6 » Sun May 13, 2007 7:06 am UTC

I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.

So I'm only 1% genius.
3.14159265... wrote:What about quantization? we DO live in a integer world?

crp wrote:oh, i thought you meant the entire funtion was f(n) = (-1)^n
i's like girls u crazy

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Postby musicinmybrain » Sun May 13, 2007 1:26 pm UTC

adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.

So I'm only 1% genius.


I assume they would be much easier for a mathematician (maybe even trivial, if you're well-educated and clever enough mathematically, particularly in number theory) and somewhat easier for a very experienced programmer.

However, you do realize the beginning ones are simple brute force problems and you have to use more math and come up with better algorithms as you go on?

If they're all really a waste of your time, bully for you.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

User avatar
Pathway
Leon Sumbitches...?
Posts: 647
Joined: Sun Oct 15, 2006 5:59 pm UTC

Postby Pathway » Sun May 13, 2007 4:44 pm UTC

adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.

So I'm only 1% genius.


The first ones are cake. They aren't all easy.
SargeZT wrote:Oh dear no, I love penguins. They're my favorite animal ever besides cows.

The reason I would kill penguins would be, no one ever, ever fucking kills penguins.

User avatar
Jach
Posts: 167
Joined: Sat May 05, 2007 8:38 pm UTC
Contact:

Postby Jach » Mon May 14, 2007 12:16 am UTC

Sort them by difficulty and then try the bottom ones. =P Or even the middle ones.

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Postby musicinmybrain » Mon May 14, 2007 12:37 am UTC

So I just hit 50%. Does that make me a half-wit? I've got half a mind to make more awful puns, but I'll refrain.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

User avatar
adlaiff6
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?
Contact:

Postby adlaiff6 » Mon May 14, 2007 3:20 am UTC

musicinmybrain wrote:
adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.

So I'm only 1% genius.


I assume they would be much easier for a mathematician (maybe even trivial, if you're well-educated and clever enough mathematically, particularly in number theory) and somewhat easier for a very experienced programmer.

However, you do realize the beginning ones are simple brute force problems and you have to use more math and come up with better algorithms as you go on?

If they're all really a waste of your time, bully for you.


Well, I like to advertise myself as a combination mathematician and theoretical computer scientist, so you're on the right track.

I did look at the last ones, and they all either seem to be either a mathematical trick, or a reasonably simple programming paradigm, like backtracking or dynamic programming.

I dunno. I think it was more a "this is a waste of my time; I have other things I should be programming if I'm going to be programming with the time I have" problem than a "man these problems suck" problem. Don't get me wrong, there were some cool problems, I just don't really see the point. Maybe I'll get more bored over the summer. Probably not though.
3.14159265... wrote:What about quantization? we DO live in a integer world?

crp wrote:oh, i thought you meant the entire funtion was f(n) = (-1)^n
i's like girls u crazy

User avatar
FiddleMath
Posts: 245
Joined: Wed Oct 11, 2006 7:46 am UTC
Location: Madison, WI
Contact:

Postby FiddleMath » Mon May 14, 2007 6:54 am UTC

adlaiff6 wrote:I dunno. I think it was more a "this is a waste of my time; I have other things I should be programming if I'm going to be programming with the time I have" problem than a "man these problems suck" problem. Don't get me wrong, there were some cool problems, I just don't really see the point. Maybe I'll get more bored over the summer. Probably not though.


Which is actually why I stopped playing on TopCoder, after a while. Once I learned the languages I was using, well enough to be slightly competitive, I wanted to actually make stuff.

themuffinking
Posts: 52
Joined: Sat Mar 10, 2007 4:42 am UTC

Postby themuffinking » Wed May 16, 2007 12:38 am UTC

I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.

Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Postby musicinmybrain » Wed May 16, 2007 12:58 am UTC

themuffinking wrote:I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.

Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?


Your length is right, so maybe you're throwing away some possibilities.

Project Euler wrote:Once the chain starts the terms are allowed to go above one million.


Is that what you're missing, perhaps?
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

Elevator_Hazard
Posts: 39
Joined: Wed Apr 25, 2007 1:35 am UTC
Location: Illinois
Contact:

Postby Elevator_Hazard » Fri May 18, 2007 1:41 am UTC

Some of that stuff I have never heard of/learned in school... Hmmm...
Image

johnw188
Posts: 26
Joined: Wed Feb 28, 2007 7:46 am UTC

Postby johnw188 » Sun May 20, 2007 6:51 am UTC

themuffinking wrote:I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.

Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?


I get 837799. Don't have my own source handy, but its pretty much the same as this solution, in ruby

def next_num(n)
n % 2 == 0 ? n / 2 : 3 * n + 1
end

sequences = {}

max_sequence_start = 0
max_sequence_length = 0

sequence_length = 0
sequence_number = 0

1.upto(999999) do |num|

sequence_length = 1

sequence_number = num

while sequence_number > 1
unless sequences[sequence_number]
sequence_number = next_num(sequence_number)
sequence_length += 1
else
sequence_length += (sequences[sequence_number] - 1)
break
end
end

sequences[num] = sequence_length

if sequence_length > max_sequence_length
max_sequence_start = num
max_sequence_length = sequence_length
end

end

puts "Solution: #{max_sequence_start} = #{max_sequence_length}"

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Postby musicinmybrain » Sun May 20, 2007 12:51 pm UTC

johnw188 wrote:I get ######. Don't have my own source handy, but its pretty much the same as this solution, in ruby


I was trying to avoid posting solutions, but since you did, I'll confirm it and post my Python code. Can we agree not to post spoilers for other problems, though? I like that spoilers aren't really out there anywhere for Project Euler. Can't stop you, of course, if you disagree.

Code: Select all

starter = 1
term = 1
count = 0
hashes = {1:0}
this_sequence = []
best_starter = 1

while starter < 1000000:
   this_sequence.append(term)
   if term in hashes:
      hashes.update(dict(zip(this_sequence, xrange(len(this_sequence) - 1 + hashes[term], hashes[term] - 1, -1))))
      if hashes[starter] > hashes[best_starter]:
         best_starter = starter
      while starter in hashes:
         starter += 1
      term = starter
      this_sequence = []
   elif term & 1: # if odd
      term = 3 * term + 1
   else:
      term >>= 1

print best_starter


Runs in 23 seconds on my 1.9 GHz P4; there's surely a more efficient way, but it works.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

User avatar
Agent Anderson
Posts: 25
Joined: Mon May 21, 2007 11:44 am UTC

Postby Agent Anderson » Fri Jun 08, 2007 11:43 pm UTC

Image

Rule number one: You don't talk about Project Euler solutions.
Rule number two: You don't talk about Project Euler solutions!

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Project Euler

Postby masher » Wed Sep 03, 2008 6:28 am UTC

Hi all

I've just discovered Project Euler and have been neglecting work to get some problems done...

I've gotten stuck on number 10; here's my code:

Spoiler:

Code: Select all



import java
.math.BigInteger;


public class Euler0010
{
    //generate a boolean array in which all primes are true
    static boolean[] primes(int max)
    {
        boolean[] primes = new boolean[max + 1];
        //assume all ints are prime
        for(int i = 0; i < primes.length; i++)
            primes[i]=true;

        //Sieve them all!!!
        for(int i = 2; i < primes.length; i++)
        {
            if(primes[i])
            {
                for(int j = i; i*< primes.length && i*>=0; j++) //work around to get over ints overflowing
                    primes[i*j] = false;
            }
        }
        return primes;
    }

    public static void main(String args[]) throws Exception
    
{
        int max = 2000000;
        BigInteger sum = new BigInteger("0");
        boolean[] prime = primes(max);

        for(int i = 2; i < prime.length; i++)
        {
            if(prime[i])
                sum = sum.add(new BigInteger(+ ""));
        }
        System.out.println(sum);
    }
}

 


The answer I get
Spoiler:
142889228620

is not accepted by the website.

Can anyone see where I've gone wrong?

shrdlu
Posts: 32
Joined: Sun Dec 09, 2007 2:00 pm UTC

Re: Project Euler

Postby shrdlu » Wed Sep 03, 2008 7:57 am UTC

To get the correct answer, you need to change exactly one character in the primes function.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Wed Sep 03, 2008 10:38 am UTC

Didn't we already have a project euler thread? Or did we just hijack other threads?

Anyway, my solution for problem 10:

Code: Select all

sum . takeWhile (<2000000) $ primes
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Re: Project Euler

Postby masher » Thu Sep 04, 2008 2:05 am UTC

shrdlu wrote:To get the correct answer, you need to change exactly one character in the primes function.



Got it. Now I just need to figure out why it worked...

Spoiler:
j=2, not j=i.

The answer is 142913828922

User avatar
Cartofel
Posts: 28
Joined: Mon May 05, 2008 3:51 pm UTC

Re: Project Euler

Postby Cartofel » Thu Sep 04, 2008 11:02 am UTC

Here's my solution in J:

Code: Select all

+/ i. &. (p:^:_1) x: 2e6


Not that it's really very helpful.
http://www.jsoftware.com :wink:
Thus spake Cartofel.
And yea, there were great rollings of eyes, and shakings of heads.

Spoiler:
I've actually never listened to any Hard-Fi

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7312
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: Project Euler

Postby Zamfir » Sat Sep 06, 2008 11:48 am UTC

I've seen a few of those J entries in project Euler, but there seems to be absolutely no point to the language except for making one-liners for Project Euler. Am I missing something, or those PE entries not representative?

User avatar
Cartofel
Posts: 28
Joined: Mon May 05, 2008 3:51 pm UTC

Re: Project Euler

Postby Cartofel » Sat Sep 06, 2008 8:24 pm UTC

Well... J is quite efficient (owing in part to the compactness of the code etc.). But you can do almost all of the things you could do with, say, C++, and perhaps those too, if you write a DLL.

If you want a few examples of things people have done with J (in many, many fewer lines than it would take in another language), look at http://www.jsoftware.com/jwiki/Showcase .
Thus spake Cartofel.
And yea, there were great rollings of eyes, and shakings of heads.

Spoiler:
I've actually never listened to any Hard-Fi

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Project Euler

Postby Briareos » Sun Sep 07, 2008 6:42 am UTC

Here's my C solution to number 10:

Spoiler:

Code: Select all

#include <stdio.h>

#define NUM_PRIMES 200000
#define LIMIT 2000000

int next_prime(int *known, int largest)
{
   int test = largest + 2;
   int i;
   for (i = 1; known[i] > 0; i++) {
      if (!(test % known[i])) {
         test += 2;
         i = 0;
      }
   }
   return test;
}

int main(int argc, char **argv)
{
   long long sum = 5;
   int primes[NUM_PRIMES];
   primes[0] = 2;
   primes[1] = 3;
   int j;
   for (j = 2; j < NUM_PRIMES; j++) {
      primes[j] = -1;
      int x = next_prime(primes, primes[j-1]);
      primes[j] = x;
      if (x >= LIMIT) {
         printf("%lld\n", sum);
         return 0;
      }
      sum += x;
   }
   printf("largest: %d\n", primes[NUM_PRIMES - 1]);
   return 0;
}
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Project Euler

Postby mrkite » Sun Sep 07, 2008 7:10 am UTC

Zamfir wrote:I've seen a few of those J entries in project Euler, but there seems to be absolutely no point to the language except for making one-liners for Project Euler.


J is based on APL, which is a formula-based programming language that's still used by IBM big iron. The bitch of APL is that it uses a non-ascii character set.

Here's conway's game of life in APL:
Image

J basically removes the special character set.

User avatar
thoughtfully
Posts: 2244
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Project Euler

Postby thoughtfully » Sun Sep 07, 2008 5:29 pm UTC

[tongue-in-cheek]
Haven't you read the unix fortunes? APL is the butt of every third joke, it seems sometimes. Good-naturedly, of course.
Unix fortune database wrote:'Tis the dream of every programmer,
ere his life is done
to write three lines of APL
and make the damn thing run.

A lot of people might say that the bitch of APL is that its more of a write-only language than PERL :)
Which isn't to say that it can't be useful or fun. Very useful, if you are using a 300 baud teletype :)
[/tongue-in-cheek]
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Sun Sep 07, 2008 10:29 pm UTC

One problem I seem to be running into a lot is overflow. I'm solving most of the problems using C. Are there any good tricks to avoiding overflow?

If it helps, one problem I ran into trouble with was number 14.

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Re: Project Euler

Postby masher » Mon Sep 08, 2008 1:19 am UTC

I've done quite a bit of brute forcing so far, probably not in the Euler spirit, but I'm just learning....

I use the BigInteger class in java.

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Mon Sep 08, 2008 2:13 am UTC

I had thought about implementing something like that, but I'll see what I come up with on a per problem basis.

I'm pretty happy that I solved number 9 with close to the optimal solution.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Mon Sep 08, 2008 3:22 am UTC

Compensating for overflow in certain problems: Modular exponentiation.
Also, longs are good for most problems. Unsigned longs can be twice as big, which means they'll be good for twice the number of problems.*

*Yes, I know it's a fallacy.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Mon Sep 08, 2008 8:05 am UTC

Berengal wrote:Also, longs are good for most problems. Unsigned longs can be twice as big


Java has the nice property that the sizes of int and long are specified by the language. This is not so by C and C++, where the size of int and long depend on the compiler, which in turn depends on which hardware it was written for.

Pesto, on many C implementations int and long are the same size. You may be able to use the 'long long' type instead. Write a program to print out sizeof(long) and sizeof(long long) to see what's up in your case. Note that the long long type is part of the C99 standard, and if you are running a C compiler in C89 conforming mode then it won't recognise it.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Project Euler

Postby mrkite » Mon Sep 08, 2008 8:14 am UTC

jaap wrote:This is not so by C and C++, where the size of int and long depend on the compiler, which in turn depends on which hardware it was written for.


That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.

User avatar
hotaru
Posts: 1025
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Project Euler

Postby hotaru » Mon Sep 08, 2008 9:37 am UTC

mrkite wrote:That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.

it's C99, not POSIX, that gave us that.

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Mon Sep 08, 2008 2:00 pm UTC

While we're on the subject, can anyone give a few hints as to a quick test for semi-primality (exactly 2, not necessarily distinct factors)?
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Mon Sep 08, 2008 4:22 pm UTC

Seeing as that's what cryptography is based on, I'm going to guess the answer is no.

hotaru wrote:
mrkite wrote:That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.

it's C99, not POSIX, that gave us that.


I'm fairly sure my current version of gcc doesn't support C99. Hell, I only learned about C99 a week or two ago.

I am, how-do-you-say-in-this-country, out of the loop.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Project Euler

Postby Ended » Mon Sep 08, 2008 7:21 pm UTC

spdqbr wrote:While we're on the subject, can anyone give a few hints as to a quick test for semi-primality (exactly 2, not necessarily distinct factors)?

Fermat's method works well if N has a factor near sqrt(N). Might be worth a try.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Project Euler

Postby mrkite » Mon Sep 08, 2008 8:51 pm UTC

Pesto wrote:I'm fairly sure my current version of gcc doesn't support C99. Hell, I only learned about C99 a week or two ago.


gcc 3+ supports C99 but it needs to be in c99 mode. However, stdint.h has been a part of the GNU C library since 1997.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Wed Sep 10, 2008 6:19 pm UTC

Speaking of solutions to problem 10, here's what I used in Python:
Spoiler:

Code: Select all

def psieve(n): #returns a list of primes up to and including n
   primelist=[]
   markedlist=[0]*(int(n)+1)
   for i in range(2,int(n)+1):
      if (markedlist[i]==0):
         primelist += [i]
         for m in range(i*2, int(n)+1, i):
            markedlist[m]=1
   return primelist

Only been using Python for a week or two, and haven't had the time to properly learn it, but I was able to write this on my own. And only with a few syntax errors. :)
To actually get the solution, I just used sum(psieve(2000000)). Well, okay, first I used a stupid brute force method. This sieve algorithm cut down the run time from 100 to 1.5 seconds. Any improvements to the above are welcome.

Bobobo
Posts: 11
Joined: Sun Aug 31, 2008 2:37 am UTC
Location: Melbourne

Re: Project Euler

Postby Bobobo » Sun Sep 14, 2008 10:47 am UTC

why is my sieve so slow? the one above me takes 0.0940001010895 seconds to run, for n = 100,000 whereas mine takes 85.8440001011:

Code: Select all

import time
def prsieve(N):
    'Returns all primes <= N in list prim'
    prim = []
    prim = range(2,N+1)
    n = 0
    p = 0
    while p <= N**.5:
        p = prim[n]
        for x in prim:
            if x%p == 0 and x != p:
                prim.remove(x)
        n += 1
    return prim

t = time.time()
prsieve(100000)
print time.time() - t


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 14 guests