ProjectEuler problem 35

[Tiberiu Gal]

On Wednesday, 16 May 2012 at 09:46:06 UTC, Dmitry Olshansky wrote:
> On 16.05.2012 13:26, 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];
>
> Don't ever do that. I mean allocating memory in tight cycle.
> Instead use circular buffer.  (just use the same array and wrap 
> indexes)
>
>> if( !(to!int(c) ).isPrime )
> And since  to!int can't know about circular buffers.
> You'd have roll your own. I don't think it's hard.
>
>> return false;
>> }
>> return true;
>> }



circular references are not not easy to implement or grasp ...
I want this code to be accessible for an average python 
developer, yet as efficient as if written in cpp ( well ... 
that's what D aims to do, right? )

how about this isCircularPrime ? it does run under 1 sec (thanks 
to Era and Andrea'  suggestions)

bool isCircularPrime( int n) {
	if(n < 10) return true;
	int x = n;
	int c = 0;
	int s;
	do {
		s = x%10;
		if ( (s % 2 == 0)  || (s == 5) || s == 0 ) return false;
		c++;
		x /= 10;
	} while (x > 9);
	

	int m = n;
	//writefln("start testing circular %s , %s, %s", n , m , c) ;
	for(int i = 1;  i <= c; i++) {
		m =   (m % 10) *  pow(10, c) + ( m / 10) ;
		//writefln(" testing circular %s , %s, %s", n , m , i) ;
		if( !primes[m] )
			return false;
	}
	return true;

}