ProjectEuler problem 35

[Andrea Fontana]

Original code in this thread run on my pc in ~400ms.
With my skipping method it takes just ~10ms.

But I think there're more improvement.

However using CTFE I guess time goes down to 0 ;)

On Wednesday, 16 May 2012 at 19:50:45 UTC, Era Scarecrow wrote:
>  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.