Project Euler Problem #35

June 16, 2010

Read the details of the problem here

Summary

How many circular primes are there below one million?

Solution

Again, playing catch up writing this one up too. Very straightforward brute-force solution to this one too. Just created a prime sieve and then, for each prime, simply ran through the rotations of the digits checking in the sieve for primality. I did consider creating some sort of memoization of numbers that had been checked as being a rotation of another prime but the solution ran quite quickly enough without such embellishments.

def LIMIT = 1000000
def isPrime = new boolean[LIMIT]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

def SQRT_LIMIT = (int)Math.sqrt(LIMIT)

for (i in 2..<SQRT_LIMIT) {
  if (!isPrime[i]) continue
  def j = i + i
  while (j < LIMIT) {
    isPrime[j] = false
    j += i
  }
}

def answer = 1

def i = 3
while (i < LIMIT) {
  if (isPrime[i]) {
    def ( s, n ) = [ i.toString(), 0 ]
    for (j in 1..<s.size()) {
      s = s[1..-1] + s[0]
      if (!isPrime[s.toInteger()]) break
      n++
    }
    if (n == s.size()-1) answer++
  }
  i += 2
}

This runs in 0.94 seconds. It’s necessary to initialize answer to 1 (one) as 2 is a circular prime and the main loops only checks odd numbers. Apart from that, not much else to say on this one as it’s so obvious in operation.

Conclusion

Not really a Groovy solution, more like normal Java apart from a few syntactic niceties. As such, performance was fine for the scale of the problem.

Advertisements

3 Responses to “Project Euler Problem #35”

  1. Kim Hansen Says:

    Hi keyzero,

    I am writing to you to urge you to not publish solutions to Project Euler in public.

    The availability of public solutions to Project Euler are posionous for the Project Euler community.

    For those of us, who climb the ladder “the-hard-way” by not cheating it is really a fun-spoiler to be passed by users with solution submission patterns which clealry indicate that they are using public solutions.

    Of course they are mainly cheating themselves, but they are also polluting the high score lists.

    Please help making life harder for the cheaters and remove the Project Euler solutions from the public.

    As they say on PE main page:

    I solved it by using a search engine, does that matter?

    ….there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved?

    So it is not in the spitir of project Euler to have the solutions in public.

    There is one perfect place to discuss PE solutions and that is in the PE problem threasd which open up, once a correct solution has been provided.

    I hope you will consider my request.

    I have written to several other sites, which publish PE solutions as well. please help bringing the fun back to PE.

    Best wishes

    Kim aka user slaunger on PE

    • keyzero Says:

      Hi Kim,

      Thanks for your comments.

      I do completely understand your point-of-view on this and I did go through a lot of angst on his matter before I started to write these up last year.

      However, a little bit of browsing around easily found references to PE answers – and I’m not talking just discussions or coding of the approaches – I mean the actual numerical answers themselves in a straight tabulated form. Just Google “project euler solutions” and you’ll see what I mean. In fact, I expect you’ve done that already.

      I noted this conundrum in my preface before commencing on this odyssey back in Oct 2009.

      https://keyzero.wordpress.com/2009/10/09/project-euler-a-groovy-approach/

      To use a couple of well-worn cliches, I do believe that the cat is truly out of the bag and the genie out of the bottle, so to speak, on PE questions, especially ones that are a few years old.

      Almost all of the ones I’ve done & written up were published 4+ years ago, before mid-2006, and as such only a couple of them still have an open site forum so I would be unable to discuss the Groovy solutions on them in any event. I would only tend to post my answer up there if it was significantly different to other solutions or demonstrated a particular language feature otherwise it’s just a “Me too” post.

      As Groovy is a relatively new language and has some, well, “peculiar” performance characteristics I believe, on balance, that these posts are probably more useful to people learning Groovy (which was my motivation for this) than they are to PE enthusiasts and, given the prevalence of complete solution sets out there, shouldn’t unduly detract from the latter’s enjoyment of the site.

      That said, I will commit to you that I won’t ever publish a straight answer on the blog, nor will I publish a solution to a question whose answer is not otherwise available via a Google search, and nor will I publish a solution to a question that is less that a year old – so that keeps any “cheaters” out of the Eulerian rankings based on the solutions here.

      Personally I don’t find it upsetting that some people just type in the answers and go through the rankings. Project Euler is, after all, a hobbyist pastime, not an Olympic sport sport or an academic examination (thank the Powers!) and isn’t worth getting too worked up over. I’m just happy to know how many I’ve solved & to what sort of standard and I don’t really care who is “in front” of me.

      Like yourself, as far as I can see people that just rattle in the answers from a “cheat-sheet” are just wasting their time. It’s not like anyone is going to give them a medal, scholarship or hard cash for their trouble and they’ve certainly not even learned anything in the process…so I can’t see why they’d bother.

      Best regards,

      Trevor

  2. Kim Hansen Says:

    Hi Trevor,

    Thank you for your thorough and thoughtful reply, which demonstrates that you are conscious about what you are doing.

    I do understand your point about writing something specific about Groovy, and it is a pity that almost all of the threads are locked for the first many problems.

    I am relatively new to PE as well, and my own focus is on doing efficient Python programming. My solutions run in average in less than one second for problems 1-100, and working on making my scripts efficient has taken quite some time. Often I have experienced that solutions I have made are a factor of ten faster than any of the published published for Python in the solution threads, and it has been annoying for me that threads have most often been locked, such that I have not had a possibility to share my solutions with the PE community.

    That said, I think the right way is to work with the PE community to change to solution thread system such that they are opened for new languages or new superior algorithms.

    This is definately something i will try to work on changing.

    I notice that some of your solutions are in pure Java. I do not understand the objective for publishing those as Java solutions are plentiful on the PE solution threads.

    I was not aware that there were tables with just the PE solutions. I will surely work on persuading the site owners of these tables to reconsdier publishing the solutions there.

    I agree PE is not an olympics game. Still, especially the Eulerians are very, very skillful and talented problem solvers, and an effort should be made to retain those in the PE community by not polluting the Eulerians score list with cheaters. I am therefore glad that you are not targeting the newest solutions in your posts.

    I would of course be even happier if you did not publish any solutions at all, despite the fact that the jeenie has come out of the bottle as you say.

    Best wishes,

    Kim


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: