View mode: basic / threaded / horizontal-split · Log in · Help
May 16, 2012
ProjectEuler problem 35
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;
}
May 16, 2012
Re: ProjectEuler problem 35
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
May 16, 2012
Re: ProjectEuler problem 35
On Wednesday, 16 May 2012 at 09:46:06 UTC, Dmitry Olshansky wrote:
> On 16.05.2012 13:26, Tiberiu Gal wrote:

>> foreach(i; 2 .. Max) {
>> //writefln("is %s prime ? %s ", i, i.isPrime);
>> if( i.isPrime && i.isCircularPrime) {
>> cnt++;

 Curiously i've just posted a sample (as part of another topic) 
that progressively gives your larger primes. I haven't speed 
tested it, but it always spits out primes.

http://forum.dlang.org/thread/jovicg$jta$1@digitalmars.com

So your code might look like...

primes_walk pw;
pw.cap = 1_000_000;

 foreach(i; pw) {
 if( i.isCircularPrime) { //i is always prime


>> 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)

 Hmm... I'd say this is totally written wrong... Rewriting it to 
a more optimized one I got 15ms as a total running time for 
1_000_000 numbers. answer I got was 3181... remember I'm not 
optimizing it or anything.

 If this is a gem to show the power & speed of D, by all means 
use it. But I want credit for my prime_walk...

real    0m0.257s
user    0m0.015s
sys     0m0.015s


-- rewrite with prime_walk
module te35;

import std.stdio;

//prime_walk by Era Scarecrow.
//range of primes, nearly O(1) for return.
struct prime_walk {
  int map[int];
  int position = 2;
  int cap = int.max;

  int front() {
    return position;
  }

  void popFront() {
    //where the real work is done.

    if ((position & 1) == 0) {
      position++;
    } else if (position>= cap) {
      throw new Exception("Out of bounds!");
    } else {
      int div = position;
      int p2 = position * 3;

      //current spot IS a prime. So...
      if (p2 < cap)
        map[p2] = div;

      position += 2;

      //identify marked spot, if so we loop again.
      while (position in map) {
        div = map[position];
        map.remove(position);
        p2 = position;
        do
          p2 += div * 2;
        while (p2 in map);

        position += 2;
        if (p2 <= cap)  //skip out, no need to save larger than 
needed values.
          map[p2] = div;
      }
    }
  }

  bool empty() {
    return position >= cap;
  }
}


const Max = 1_000_000;

bool[Max] primes;

void main() {
  assert(bool.init == false);  //just a speedup if true. removes 
15ms
  int cnt;
  prime_walk pw;
  pw.cap = Max; //no primes larger than 1Mil

  foreach(i; pw) { //i is ALWAYS prime.
    primes[i] = true;  //removes need for isprime totally if we 
are never going above the foreach's i
    if(i.isCircularPrime) {
      cnt++;
//      writefln("\t\tis %s, circular prime ", i); //already 
confirmed
    }
  }

  writeln(cnt);

}

//bool isPrime(int); //removed, not needed in this case

//since it's always lower...
//removes need for string, and only uses 1 division per level
immutable int[] levels = [
//1_000_000_000, 100_000_000, 10_000_000,  //completeness sake.
1_000_000, 100_000, 10_000, 1_000, 100, 10];

bool isCircularPrime(int n) {

  foreach(l; levels) {
    if (l > n)
      continue;

    if (primes[n] == false)
      return false;

    n %= l; //remainder of 10, sorta...
  }
  return true;
}
May 16, 2012
Re: ProjectEuler problem 35
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;
> }
May 16, 2012
Re: ProjectEuler problem 35
The correct answer is 55
Your versions of isCircularPrime just truncates the number ( this 
is actually useful in a next problem though; )

prime_walks is a nice and efficient way to find primes ... and 
not a bit n00bfriendly.

I'm not posting it anywhere, I'm just learning and having fun.


On Wednesday, 16 May 2012 at 10:38:02 UTC, Era Scarecrow wrote:
> On Wednesday, 16 May 2012 at 09:46:06 UTC, Dmitry Olshansky 
> wrote:
>> On 16.05.2012 13:26, Tiberiu Gal wrote:
>
>>> foreach(i; 2 .. Max) {
>>> //writefln("is %s prime ? %s ", i, i.isPrime);
>>> if( i.isPrime && i.isCircularPrime) {
>>> cnt++;
>
>  Curiously i've just posted a sample (as part of another topic) 
> that progressively gives your larger primes. I haven't speed 
> tested it, but it always spits out primes.
>
> http://forum.dlang.org/thread/jovicg$jta$1@digitalmars.com
>
> So your code might look like...
>
> primes_walk pw;
> pw.cap = 1_000_000;
>
>  foreach(i; pw) {
>  if( i.isCircularPrime) { //i is always prime
>
>
>>> 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)
>
>  Hmm... I'd say this is totally written wrong... Rewriting it 
> to a more optimized one I got 15ms as a total running time for 
> 1_000_000 numbers. answer I got was 3181... remember I'm not 
> optimizing it or anything.
>
>  If this is a gem to show the power & speed of D, by all means 
> use it. But I want credit for my prime_walk...
>
> real    0m0.257s
> user    0m0.015s
> sys     0m0.015s
>
>
> -- rewrite with prime_walk
> module te35;
>
> import std.stdio;
>
> //prime_walk by Era Scarecrow.
> //range of primes, nearly O(1) for return.
> struct prime_walk {
>   int map[int];
>   int position = 2;
>   int cap = int.max;
>
>   int front() {
>     return position;
>   }
>
>   void popFront() {
>     //where the real work is done.
>
>     if ((position & 1) == 0) {
>       position++;
>     } else if (position>= cap) {
>       throw new Exception("Out of bounds!");
>     } else {
>       int div = position;
>       int p2 = position * 3;
>
>       //current spot IS a prime. So...
>       if (p2 < cap)
>         map[p2] = div;
>
>       position += 2;
>
>       //identify marked spot, if so we loop again.
>       while (position in map) {
>         div = map[position];
>         map.remove(position);
>         p2 = position;
>         do
>           p2 += div * 2;
>         while (p2 in map);
>
>         position += 2;
>         if (p2 <= cap)  //skip out, no need to save larger than 
> needed values.
>           map[p2] = div;
>       }
>     }
>   }
>
>   bool empty() {
>     return position >= cap;
>   }
> }
>
>
> const Max = 1_000_000;
>
> bool[Max] primes;
>
> void main() {
>   assert(bool.init == false);  //just a speedup if true. 
> removes 15ms
>   int cnt;
>   prime_walk pw;
>   pw.cap = Max; //no primes larger than 1Mil
>
>   foreach(i; pw) { //i is ALWAYS prime.
>     primes[i] = true;  //removes need for isprime totally if we 
> are never going above the foreach's i
>     if(i.isCircularPrime) {
>       cnt++;
> //      writefln("\t\tis %s, circular prime ", i); //already 
> confirmed
>     }
>   }
>
>   writeln(cnt);
>
> }
>
> //bool isPrime(int); //removed, not needed in this case
>
> //since it's always lower...
> //removes need for string, and only uses 1 division per level
> immutable int[] levels = [
> //1_000_000_000, 100_000_000, 10_000_000,  //completeness sake.
> 1_000_000, 100_000, 10_000, 1_000, 100, 10];
>
> bool isCircularPrime(int n) {
>
>   foreach(l; levels) {
>     if (l > n)
>       continue;
>
>     if (primes[n] == false)
>       return false;
>
>     n %= l; //remainder of 10, sorta...
>   }
>   return true;
> }
May 16, 2012
Re: ProjectEuler problem 35
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;
>> }
May 16, 2012
Re: ProjectEuler problem 35
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;
>>> }
May 16, 2012
Re: ProjectEuler problem 35
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;

}
May 16, 2012
Re: ProjectEuler problem 35
"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;
>>>> }
May 16, 2012
Re: ProjectEuler problem 35
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;
>>>>> }
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home