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
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
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
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
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)
I used the blockwise parallel sieve described here, and measured
nice speed-ups as described in his blog. It completes
calculations within
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 (
c/pascal/haskell code)
I used the blockwise parallel sieve described here, and
measured nice speed-ups
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
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
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
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
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.
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
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
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
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.
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
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 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
On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
The correct answer is 55
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
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
20 matches
Mail list logo
