ProjectEuler problem 35

[Tiberiu Gal]

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