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