Thread overview | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
May 16, 2012 ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
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; } |
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tiberiu Gal | 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; > } -- Dmitry Olshansky |
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | 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; } |
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tiberiu Gal | 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;
> }
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Era Scarecrow | 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;
> }
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrea Fontana | 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;
>> }
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tiberiu Gal | 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;
>>> }
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | 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;
}
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrea Fontana | "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;
>>>> }
|
May 16, 2012 Re: ProjectEuler problem 35 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tiberiu Gal | 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:
>>>> 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;
>>>>> }
|
Copyright © 1999-2021 by the D Language Foundation