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