AWK - 129 bytes
...oookay... too long to win points for compactness... but maybe it can gain some honor for the speed?
The x
file:
BEGIN{n=2;i=0;while(n<1366662){if(n in L){p=L[n];del L[n]}else{P[p=n]=++i;if(i in P)print n}j=n+p;while(j in L)j=j+p;L[j]=p;n++}}
Running:
$ awk -f x | nl | tail
9991 1365913
9992 1365983
9993 1366019
9994 1366187
9995 1366327
9996 1366433
9997 1366483
9998 1366531
9999 1366609
10000 1366661
Readable:
BEGIN {
n=2
i=0
while( n<1366662 ) {
if( n in L ) {
p=L[n]
del L[n]
} else {
P[p=n]=++i
if( i in P ) print n
}
j=n+p
while( j in L ) j=j+p
L[j]=p
n++
}
}
The program computes a stream of primes using L
as "tape of numbers" holding found primes jumping around on L
to flag the nearby numbers already known to have a divisor. These jumping primes will advance while the "tape of numbers" L
is chopped off number by number from its beginning.
While chopping off the tape head L[n]
being empty means there is no known (prime) divisor.
L[n]
holding a value means, this value is a prime and known to divide n
.
So either we have found a prime divisor or a new prime.
Then ths prime will be advanced to the next L[n+m*p]
on the tape found being empty.
This is like the Sieve of Eratosthenes "pulled thru a Klein's bottle". You always act on the tape start. Instead of firing multiples of primes thru the tape, you use the primes being found already as cursors jumping away from the tape start by multiple distances of their own value until a free position is found.
While the outer loop generates one prime or not prime decission per loop, the primes found get counted and stored in P
as key, the value of this (key,value) pair is not relevant for the program flow.
If their key i
happens to be in P
already (i in P
), we have a prime of the p(p(i)) breed.
Running:
$ time awk -f x.awk | wc -l
10000
real 0m3.675s
user 0m3.612s
sys 0m0.052s
Take into account that this code does not use external precalculated prime tables.
Time taken on my good old Thinkpad T60, so I think it deserves to be called fast.
Tested with mawk
and gawk
on Debian8/AMD64
2You should generally try to post challenges in the sandbox first (see the link on the right side) in order to work out the issues. – aditsu quit because SE is EVIL – 2015-10-23T17:43:31.230
6Optimizing for runtime is not what we do in a code-golf challenge; the shortest program always wins. – lirtosiast – 2015-10-23T18:53:09.507
1
Primes with prime subscripts: A006450.
– None – 2015-10-23T21:55:27.8271
@bilbo Answers for code golf are usually accepted after a week, and should be accepted as the shortest successful code. If you wanted code speed, there is a tag for that. See this page about the tag code-golf.
– Addison Crump – 2015-10-24T12:04:35.140The answer you accepted isn't even the fastest. My Matlab/Octave answer runs in 0.16 seconds, and I'd imagine the (winning by size) J answer by @ZGarb has a similar runtime. – lirtosiast – 2015-10-25T05:03:19.097
So weird I just did this the other day for a different reason in excel haha, small world of tasks – Albert Renshaw – 2015-10-25T06:46:39.173
@ThomasKwa: I was surprised by seeing my answer as accepted one too. Maybe that decision can be undone? I would prefer that! And when it comes to speed, please distinguish solutions calculating the primes themself and the ones depending on preexisting prime functions or tables. I think, this challenge should be reworked/reworded and/or split into different variants with different rules or whatever it takes to clearness and fairness... – None – 2015-10-25T06:47:42.813
I'm new here and in my opinion, I thought the solutions execution time must be taken in consideration in shorten contests. I have attended more solutions in conventional languages. Perhaps can I add a tag related to speed but there is only fastest-algorithm and fastest-code and I attended also a shorten solution. Is it possible to remove the accepted flag for more time to the contest? – JeanClaudeDaudin – 2015-10-25T07:10:25.073
@bilbo It's considered bad practice to change the winning criterion of the contest after answers have already been posted. If you want to create a new contest scored by something other than [tag:code-golf] (shortest code), post it in the Sandbox first. (In its current form, in my opinion, this challenge wouldn't be a good fit for fastest-code or fastest-algorithm, so you'd need to change something else about it too.)
– lirtosiast – 2015-10-25T07:29:31.0831All contests need an objective winning criterion; they are off topic otherwise. If you're going to judge answers by size and speed, you need to disclose a way to combine both. This should be done when the contest is posted, not 14 hours and 10 answers later. I have undone all speed-related edits, since the only other option would be to close this post for being off topic. – Dennis – 2015-10-25T14:10:09.540