# how many project Euler problems have you solved?

SCJP

Visit my download page

it turned out to be pretty simple but i have never written code that looked like this before

so that makes 16 for me

SCJP

Visit my download page

- 2

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Stephan van Hulst wrote:I'm going to try to solve the problems using the Haskell language, since I'd like to practice it a bit.

Yeah, that's what started me off - I'm doing them in Scala. Though I'm playing with F# at the moment as well, so might switch to that (or re-implement some of my old ones).

SCJP

Visit my download page

Sheriff

SCJP

Visit my download page

Sheriff

Spot false dilemmas now, ask me how!

(If you're not on the edge, you're taking up too much room.)

Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

For no good reason, I always though having a pre-built list of primes was cheating. I wrote a few utilities that I do use, but all data is re-computed each time. I have a helper class that you can say "Build the first X prime numbers", and then you can say "get the next prime number"...maybe I should add "get the NEXT x prime numbers".

Like I said, it's my own, weird rule, but I think everyone has to do it their own way.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

There's one I completed that I feel a bit guilty about. I had an intuition that the answer probably followed a particular pattern. That gave me a lightning algorithm, and it turned out to be the right answer. But I still can't

*prove*it has to follow that pattern.

It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

i wrote a "helper" class to find primes

it is not the fastest algorithm, but it is fast enough so far(i might improve it)

i also will probably overload the method like this

public boolean isPrime(int number)

public boolean isPrime(BigInteger number)

i noticed that BigInteger has a method isProbablyPrime() but i am not sure how useful it might be

SCJP

Visit my download page

i had to set a limit for a loop and i used what seemed right even though i wasn't positive. it worked

SCJP

Visit my download page

Some colleagues and I did a lunchtime language club, and part of it was solving Euler problems in Ruby and Python. We'd do a few during the week, then get together and compare our solutions. Then the problems got harder and we got busier, and it all just petered out. I really would like to get to at least 100 someday.

Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

Haha, actually I made a utility class called Primes which determines if an integer is a prime number, does prime factorization, and some other stuff, because I have the feeling I'm going to need them a lot

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

(edit: oh, I see I didn't post the Haskell version there, those are only in Scala. But my Haskell version was very much like the second Scala version).

Stephan van Hulst wrote:Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

Haha, actually I made a utility class called Primes which determines if an integer is a prime number, does prime factorization, and some other stuff, because I have the feeling I'm going to need them a lot

I have an EulerUtils class with a dozen methods in. I like the idea of a utility class named Primes, except I also have a bunch of methods that work with series and collections.

I think anything is effective to learn a new language. Most of the time, you just need to work on something, anything at all, to get a kickstart. Project Euler provides an entertaining way to do so.

I usually test my proficiency in a language by taking a game like Chess and writing a text based implementation for the command line, then I add a GUI, and LAN capabilities. If I can do those things in a readable, self-documenting way, I feel I understand most of the language.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Matthew Brown wrote:Yeah, that won't cut it when you get onto some of the more computationally expensive questions. Mine uses a Sieve of Eratosthenes (either all in one if I know how high I need to go, or incremental if I don't). For problems where I have to work out if something is a prime number I generate them in advance and shove them in a HashSet for quick lookup.

I have a nice sieve implementation for when I know how high to go. I can't quite crack the problem of an incremental sieve, though. In the first case, if k is the prime number whose multiples I am filtering out, I know I can stop sifting when k has a certain property in relation to the upper limit. If, instead, I need n prime numbers, I can't figure out how to know when my sifting is done.

then i'd test 23 to see if it is divisible by 2, then 3, then quit since 5*5 > 23. since 23 has no divisors, it must be prime.

it now becomes my largestPrimeFound, and I can generate the next by starting at 25 (which fails after 3 tests).

I've never figured out my big-O notation on it, but I think it would be somehow related to whatever the distribution of primes is...[edit - according to my brief research, this would be log-n]

I think I also have methods that say "find the first X primes" and "find the first prime larger than X"

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

fred rosenberger wrote:If the largest i've found is 19, i'd test 21 to see if it is divisible by 2, then 3, at which point i'd quit since 21%3 == 0.

then i'd test 23 to see if it is divisible by 2, then 3, then quit since 5*5 > 23. since 23 has no divisors, it must be prime.

Seems like we should be able to dispense with the divisible by 2 test since we already know we're getting an odd number.

As an example, let's say I was looking for the 60th prime number. I'd do a sieve on 1-100. That gives me 25 prime numbers, so I know I need to keep going. So I look at 101-200 - but I just need to eliminate multiples of primes I've already found up to sqrt(200). I've now got 46 primes, so I look at the next 100. And so on, until I've got enough. So I'll (probably) generate more than I need, but not by much.

I've been stuck on #15 for a while. Mostly with Java, but I've been going over the same ones with Python as I learn that. I'm finding Python to be really friendly.

Matthew Brown wrote:My incremental sieve works by looking at the next chunk of 100 numbers, and using the usual sieve technique using the prime numbers I've already generated.

As an example, let's say I was looking for the 60th prime number. I'd do a sieve on 1-100. That gives me 25 prime numbers, so I know I need to keep going. So I look at 101-200 - but I just need to eliminate multiples of primes I've already found up to sqrt(200). I've now got 46 primes, so I look at the next 100. And so on, until I've got enough. So I'll (probably) generate more than I need, but not by much.

I'd suppose that it is possible to obtain some approximation of how many numbers you need to test to get first

*N*primes (and indeed there is), so you could start with that and only do incremental search if the approximation was too low.

(I'd have to look the formula up. I'm not sure that would count as cheating - for me it is enough that I was able to figure out something like that should exist. It is actually much simpler than I expected (as many other math tricks), but still I don't think I'd be able to work that out on my own in the time I'd be willing to put into it.)

don't feel bad Tim i haven't solved #15 yet either

SCJP

Visit my download page

i am sure you are right it is not that hard

#31 is the one giving me a hard time right now

SCJP

Visit my download page

Overview Source

Stephan van Hulst wrote:Since there has been some talk of prime numbers, I figured it'd be fun to make a fluent interface version of my Primes utility in Java.

static Iterable<Integer> greaterThan(int value)

Returns all prime numbers greater than or equal to a specified value.

How is this possible?

Dennis Deems wrote:static Iterable<Integer> greaterThan(int value)

Returns all prime numbers greater than or equal to a specified value.

How is this possible?

It doesn't actually return an infinite number of primes. It returns an iterator that will generate as many primes as it is asked to. So stick it in a for loop and it will run forever (or until you run out of memory). It's a sort of lazy generation.