## digitalmars.D.learn - ProjectEuler problem 35

• Tiberiu Gal (57/57) May 16 2012 hi
• Dmitry Olshansky (7/59) May 16 2012 Don't ever do that. I mean allocating memory in tight cycle.
• Era Scarecrow (98/111) May 16 2012 Curiously i've just posted a sample (as part of another topic)
• Tiberiu Gal (7/120) May 16 2012 The correct answer is 55
• Era Scarecrow (24/36) May 16 2012 Hmm glancing at the original source I see what you mean. A
• Andrea Fontana (5/44) May 16 2012 Original code in this thread run on my pc in ~400ms.
• Tiberiu Gal (29/107) May 16 2012 circular references are not not easy to implement or grasp ...
• Stewart Gordon (7/9) May 19 2012
• maarten van damme (5/5) May 19 2012 A huge optimization could be made by storing and int array of already
• Stewart Gordon (7/12) May 20 2012 Do you mean build an array of already-found primes and use them to test ...
• Jay Norwood (5/12) May 20 2012 This person has done a number of optimizations. He gets some
• Andrea Fontana (4/61) May 16 2012 What about some logic optimizations?
• Jay Norwood (6/9) May 19 2012 I used the blockwise parallel sieve described here, and measured
• Era Scarecrow (6/17) May 19 2012 Curiously I've done most of these (Although not exactly as
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```hi

many claim their code solves the problem in order of ms (

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
Dmitry Olshansky <dmitry.olsh gmail.com> writes:
```On 16.05.2012 13:26, Tiberiu Gal wrote:
hi

many claim their code solves the problem in order of ms (

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
"Era Scarecrow" <rtcvb32 yahoo.com> writes:
```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.

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
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```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.

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
"Era Scarecrow" <rtcvb32 yahoo.com> writes:
```  On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
Your versions of isCircularPrime just truncates the number (
this is actually useful in a next problem though; )

Hmm glancing at the original source I see what you mean. A
slight modification to fill primes with bools primes beforehand
and a slight re-write of the circular check code would do the
trick.

And after doing so I still end up with about the same speed,
course the second run I was doing a foreach on bool[] primes, and
not on prime_walk, but you get the idea... Unless you really need
to see it I won't repost my changes here.

On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
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...

I went ahead and tried that.. It varied the execution speed,
giving a slight speedup or a slight slowdown, but the checks are
almost not worth it. In the circular check 99% of them fail on
the first rotation. Guess it ends up as "which is cheaper?". 10
compares? or 1 divide and 1 multiply and 1 lookup?

that's true for the Circular check ... but in the whole app,
the most time is spent finding primes.

Which is why I simplified the whole code in my example.
prime_walk always returns the next prime, and using the primes
array, we instantly know if the number checked is prime. Large
portions of the code are rather wasteful in the original example,
like checking for a prime and then a circular prime.

Skipping the understanding of prime_walk, using the levels (for
the most significant digit) should be fairly self explanatory,
plus it is MUCH faster than convert to string and then convert
back again.
```
May 16 2012
"Andrea Fontana" <nospam example.com> writes:
```Original code in this thread run on my pc in ~400ms.
With my skipping method it takes just ~10ms.

But I think there're more improvement.

However using CTFE I guess time goes down to 0 ;)

On Wednesday, 16 May 2012 at 19:50:45 UTC, Era Scarecrow wrote:
On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
Your versions of isCircularPrime just truncates the number (
this is actually useful in a next problem though; )

Hmm glancing at the original source I see what you mean. A
slight modification to fill primes with bools primes beforehand
and a slight re-write of the circular check code would do the
trick.

And after doing so I still end up with about the same speed,
course the second run I was doing a foreach on bool[] primes,
and not on prime_walk, but you get the idea... Unless you
really need to see it I won't repost my changes here.

On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
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...

I went ahead and tried that.. It varied the execution speed,
giving a slight speedup or a slight slowdown, but the checks
are almost not worth it. In the circular check 99% of them fail
on the first rotation. Guess it ends up as "which is cheaper?".
10 compares? or 1 divide and 1 multiply and 1 lookup?

that's true for the Circular check ... but in the whole app,
the most time is spent finding primes.

Which is why I simplified the whole code in my example.
prime_walk always returns the next prime, and using the primes
array, we instantly know if the number checked is prime. Large
portions of the code are rather wasteful in the original
example, like checking for a prime and then a circular prime.

Skipping the understanding of prime_walk, using the levels
(for the most significant digit) should be fairly self
explanatory, plus it is MUCH faster than convert to string and
then convert back again.

```
May 16 2012
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```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 (

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

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
Stewart Gordon <smjg_1998 yahoo.com> writes:
```On 16/05/2012 10:46, Dmitry Olshansky wrote:
<snip>
Don't ever do that. I mean allocating memory in tight cycle.
Instead use circular buffer. (just use the same array and wrap indexes)

<snip>

You might as well not use a string representation at all.  At the beginning of
the loop,
calculate the number of digits in n, then pow10 = 10 ^^ (digits - 1).  Then
cycle with

n = n / 10 + (n % 10) * pow10;

Stewart.
```
May 19 2012
maarten van damme <maartenvd1994 gmail.com> writes:
```A huge optimization could be made by storing and int array of already
found primes and test all primes smaller then half the to-test number.
this will speed up a lot.
Another huge improvement could be made with hardcoding everything up
to the prime 3 and then iterate with intervals of 2 instead of 1.
```
May 19 2012
Stewart Gordon <smjg_1998 yahoo.com> writes:
```On 19/05/2012 16:13, maarten van damme wrote:
A huge optimization could be made by storing and int array of already
found primes and test all primes smaller then half the to-test number.
this will speed up a lot.

Do you mean build an array of already-found primes and use them to test new
primes?  You
need only to try dividing by each prime up to the square root of the number
being tested.

Another huge improvement could be made with hardcoding everything up
to the prime 3 and then iterate with intervals of 2 instead of 1.

Yes, that's a common optimisation.  Faster still would be to test 6k-1 and 6k+1
for each
positive integer k.  Indeed, I've done more than this in my time: hard-coded
all the
primes up to 30 and the residues modulo 30 that can possibly be of primes above
30.

Stewart.
```
May 20 2012
"Jay Norwood" <jayn prismnet.com> writes:
```On Sunday, 20 May 2012 at 15:48:31 UTC, Stewart Gordon wrote:
On 19/05/2012 16:13, maarten van damme wrote:
Yes, that's a common optimisation.  Faster still would be to
test 6k-1 and 6k+1 for each positive integer k.  Indeed, I've
done more than this in my time: hard-coded all the primes up to
30 and the residues modulo 30 that can possibly be of primes
above 30.

Stewart.

This person has done a number of optimizations.  He gets some
speed-up by storing in bits rather than bytes.  It is also
designed for segments that fir in the L1 cache.

```
May 20 2012
"Andrea Fontana" <nospam example.com> writes:
```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 (

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
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```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:

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 (

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
"Andrea Fontana" <nospam example.com> writes:
```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:

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 (

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
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```"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:

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 (

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
"Andrea Fontana" <nospam example.com> writes:
```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:

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 (

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
"Tiberiu Gal" <galtiberiu gmail.com> writes:
```============
The number, 197, is called a circular prime because all rotations
of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17,
31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?
===========

On Wednesday, 16 May 2012 at 14:17:21 UTC, Andrea Fontana wrote:
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.

```
May 16 2012
=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
```On 05/16/2012 07:14 AM, 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.

A number that cannot be circular prime need not be checked whether
regular prime.

Ali

--
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html
```
May 16 2012
"Jay Norwood" <jayn prismnet.com> writes:
```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 (

I used the blockwise parallel sieve described here, and measured
nice speed-ups as described in his blog.  It completes
calculations within an L1 cache block before moving on.  Perhaps
you can redesign you code to do the same...

http://create.stephan-brumme.com/eratosthenes/
```
May 19 2012
"Era Scarecrow" <rtcvb32 yahoo.com> writes:
```On Saturday, 19 May 2012 at 16:43:03 UTC, Jay Norwood wrote:
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 (

I used the blockwise parallel sieve described here, and
measured nice speed-ups as described in his blog.  It completes
calculations within an L1 cache block before moving on.
Perhaps you can redesign you code to do the same...

http://create.stephan-brumme.com/eratosthenes/

Curiously I've done most of these (Although not exactly as
written). The blockwise makes sense; I've seen a prime checker JS
somewhere that uses those exact primes and if a number wasn't
divisible by them it was 'probably prime'.

All of this is good material to glance over and review though :)
```
May 19 2012