ProjectEuler problem 35

Tiberiu Gal galtiberiu at gmail.com
Wed May 16 02:26:42 PDT 2012


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


More information about the Digitalmars-d-learn mailing list