Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

how many project Euler problems have you solved?

 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i have solved 15 of them so far, but they are getting harder.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
fred rosenberger
lowercase baba
Bartender
Posts: 12180
34
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i just solved #24
it turned out to be pretty simple but i have never written code that looked like this before
so that makes 16 for me
 
Stephan van Hulst
Bartender
Pie
Posts: 6081
71
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I may have solved one or two indirectly by writing sample code for these boards. However, this thread prompted me to join as well, and I'm going to try to solve the problems using the Haskell language, since I'd like to practice it a bit. But as of now my badge looks pretty unimpressive :P

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
lol Stephan
dont worry, i believe in you
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Scala seems pretty popular. i am probably too lazy to learn it though
 
Bert Bates
author
Sheriff
Posts: 8900
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Curse you Randall!

Here I was having a perfectly happy life and now I'm sucked in. Having solved my first two I'm hooked.

Bert
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hee hee dont feel bad Bert, i am hooked also. it is kind of addictive
 
Bert Bates
author
Sheriff
Posts: 8900
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I too am hooked. I'm working on problem 6. The first 4 presented no difficulties, but I had to mull over problem 5 for some time before the light bulb went on. Curses indeed!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12180
34
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have the same feeling. I also spent quite a bit of time on a general purpose prime number generator ("give me all up to N", "give me the first N", "give me the next N") etc.

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.
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew, getting the correct answer is what matters most . i know what you mean though. i just finished solving #30
i had to set a limit for a loop and i used what seemed right even though i wasn't positive. it worked
 
Greg Charles
Sheriff
Posts: 2989
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Pie
Posts: 15435
41
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've mainly used Scala and some Haskell.

 
Jelle Klap
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
None.
 
Stephan van Hulst
Bartender
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Pie
Posts: 15435
41
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also made some Scala and Haskell prime number utilities, you can see them in this GitHub Gist.

(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).
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think I too might start learning Scala. Using Project Euler to learn a new language seems like a great idea. Do you feel it's been effective?
 
Stephan van Hulst
Bartender
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, I'd probably make a couple of other utility classes as well (or rather, Haskell files containing mathematical functions) when I need some more. I might make it all into a single file if I end up with just a small amount.

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.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12180
34
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
IIRC, to find the next prime, I start at (largestPrimeFound + 2), and start testing it with all my known primes up to the sqrt of the number. In other words, 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.

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"
 
Tim McGuire
Ranch Hand
Posts: 820
IntelliJ IDE Tomcat Server VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You guys must have overloaded the site. I can't get to it now.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Tim McGuire
Ranch Hand
Posts: 820
IntelliJ IDE Tomcat Server VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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.
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.)
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i have solved 18 of them now with 19 and 20 on the way.
don't feel bad Tim i haven't solved #15 yet either
 
fred rosenberger
lowercase baba
Bartender
Posts: 12180
34
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
15 isn't too hard, once you know the secret. it is relatively simple calculation. I can give a hint, if you want...
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i must admit, i just skipped over #15
i am sure you are right it is not that hard
#31 is the one giving me a hard time right now
 
Tim McGuire
Ranch Hand
Posts: 820
IntelliJ IDE Tomcat Server VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:15 isn't too hard, once you know the secret. it is relatively simple calculation. I can give a hint, if you want...


thanks, but I (think) I got the secret and have yet to apply it. I will let you know.
 
Dave Trower
Ranch Hand
Posts: 87
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I have done all of them in order, but I have not worked on them for a while.
 
Stephan van Hulst
Bartender
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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. Try this line:
Overview Source
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic