ProjectEuler problem 35

[Andrea Fontana]

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;
> }