ProjectEuler problem 35

[Era Scarecrow]

  On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
> The correct answer is 55
> Your versions of isCircularPrime just truncates the number ( 
> this is actually useful in a next problem though; )

  Hmm glancing at the original source I see what you mean. A 
slight modification to fill primes with bools primes beforehand 
and a slight re-write of the circular check code would do the 
trick.

  And after doing so I still end up with about the same speed, 
course the second run I was doing a foreach on bool[] primes, and 
not on prime_walk, but you get the idea... Unless you really need 
to see it I won't repost my changes here.


On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
>On Wednesday, 16 May 2012 at 14:01:19 UTC, Andrea Fontana wrote:
>> Not that big gain?
>
>> If you check for circulars numbers from 0 to 1.000.000 you can 
>> skip intervals from 200.000 to 299.999, from 400.000 to 
>> 699.999 and from 800.000 to 899.999 (and other sub-intervals, 
>> of course).
>
>> You'll skip 70% of checks...

  I went ahead and tried that.. It varied the execution speed, 
giving a slight speedup or a slight slowdown, but the checks are 
almost not worth it. In the circular check 99% of them fail on 
the first rotation. Guess it ends up as "which is cheaper?". 10 
compares? or 1 divide and 1 multiply and 1 lookup?

>
> that's true for the Circular check ... but in the whole app, 
> the most time is spent finding primes.

  Which is why I simplified the whole code in my example. 
prime_walk always returns the next prime, and using the primes 
array, we instantly know if the number checked is prime. Large 
portions of the code are rather wasteful in the original example, 
like checking for a prime and then a circular prime.

  Skipping the understanding of prime_walk, using the levels (for 
the most significant digit) should be fairly self explanatory, 
plus it is MUCH faster than convert to string and then convert 
back again.