ProjectEuler problem 35

Dmitry Olshansky dmitry.olsh at gmail.com
Wed May 16 02:46:02 PDT 2012


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


-- 
Dmitry Olshansky


More information about the Digitalmars-d-learn mailing list