Thread overview  


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  

 
Posted in reply to Tiberiu Gal  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  

 
Posted in reply to Dmitry Olshansky  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  

 
Posted in reply to Tiberiu Gal  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  

 
Posted in reply to Era Scarecrow  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  

 
Posted in reply to Andrea Fontana  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  

 
Posted in reply to Tiberiu Gal  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 subintervals, 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  

 
Posted in reply to Dmitry Olshansky  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  

 
Posted in reply to Andrea Fontana  "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 subintervals, 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  

 
Posted in reply to Tiberiu Gal  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 subintervals, 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 

Copyright © 19992016 by Digital Mars ®, All Rights Reserved