ProjectEuler problem 35

[Era Scarecrow]

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