Jump to page: 1 2
Thread overview
ProjectEuler problem 35
May 16, 2012
Tiberiu Gal
May 16, 2012
Dmitry Olshansky
May 16, 2012
Era Scarecrow
May 16, 2012
Tiberiu Gal
May 16, 2012
Era Scarecrow
May 16, 2012
Andrea Fontana
May 16, 2012
Tiberiu Gal
May 19, 2012
Stewart Gordon
May 19, 2012
maarten van damme
May 20, 2012
Stewart Gordon
May 21, 2012
Jay Norwood
May 16, 2012
Andrea Fontana
May 16, 2012
Tiberiu Gal
May 16, 2012
Andrea Fontana
May 16, 2012
Tiberiu Gal
May 16, 2012
Andrea Fontana
May 16, 2012
Tiberiu Gal
May 16, 2012
Ali Çehreli
May 19, 2012
Jay Norwood
May 19, 2012
Era Scarecrow
May 16, 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;
}
May 16, 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
May 16, 2012
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
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
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
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
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
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
"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
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