ProjectEuler problem 35

[Andrea Fontana]

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...

On Wednesday, 16 May 2012 at 13:14:37 UTC, Tiberiu Gal wrote:
> Good point there, unfortunately it's not that big a gain in 
> this particular instance.
>
> thank you
>
> On Wednesday, 16 May 2012 at 12:46:07 UTC, Andrea Fontana wrote:
>> What about some logic optimizations?
>>
>> F.E. if number contains one of these digit 0,2,4,6,8,5 is not 
>> circular of course ..
>>
>>
>> On Wednesday, 16 May 2012 at 09:26:45 UTC, Tiberiu Gal wrote:
>>> hi
>>>
>>> many claim their code solves the problem in order of ms ( 
>>> c/pascal/haskell code)
>>>
>>> my D code takes ~1.5  seconds.
>>> Can it be made faster ( without pointers )?
>>> it runs the same with or without caching the primes, and most 
>>> of the time it spends finding primes; isCircularPrime can be 
>>> optimized a bit, obviously, but it's not the bottleneck.
>>>
>>> thanks
>>>
>>> ===========================================
>>> module te35;
>>>
>>> import std.stdio, std.math, std.conv;
>>>
>>> const Max = 1_000_000;
>>>
>>> byte[Max] primes;
>>>
>>> void main() {
>>> 	primes[] = -1;
>>> 	int cnt;
>>> 	foreach(i; 2 .. Max) {
>>> 		//writefln("is %s prime ? %s ", i, i.isPrime);
>>> 		if( i.isPrime && i.isCircularPrime) {
>>> 			cnt++;
>>> 			//writefln("\t\tis %s, circular prime ? %s ", i, 
>>> i.isCircularPrime);
>>> 		}
>>> 	}
>>>
>>> 	writeln(cnt);
>>> 	
>>> }
>>>
>>> bool isPrime(int n) {
>>> 	byte x = 0;
>>> 	if( ( x = primes[n]) != -1) return (x == 1);
>>>
>>> 	if( n < 2 && n > 0 ) {
>>> 		primes[n] = 0;
>>> 		return true;
>>> 	}
>>> 	
>>> 	//int s = cast(int) (sqrt( cast(real) n) ) + 1;
>>> 	for(int i=2; i*i < n + 1; i++) {
>>> 		if( n %i == 0 ) {
>>> 			primes[n] = 0;
>>> 			return false;
>>> 		}
>>> 	}
>>> 	
>>> 	primes[n] = 1;
>>> 	return true;
>>>
>>> }
>>>
>>> bool isCircularPrime( int n) {
>>> 	
>>> 	auto c = to!string(n);
>>> 	for(int i ; i < c.length; i++){
>>> 		c = c[1 .. $] ~ c[0];
>>> 		if( !(to!int(c) ).isPrime )
>>> 			return false;
>>> 	}
>>> 	return true;
>>> }