ProjectEuler problem 35

[Andrea Fontana]

Probabily i miss the point. Are you looking for prime & circular 
primes or for circular primes only?

On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
> "You'll skip 70% of checks..."
> that's true for the Circular check ... but in the whole app, 
> the most time is spent finding primes.
>
>
> 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...
>>
>> 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;
>>>>> }