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