Priming a Pristine World

Pyth, 29 bytes

e.f>}ZPZsmq1lPs.D`Z}Fd.CU`Z2Q

Golfing, explanation, etc. to follow.

CJam, 51 bytes

1ri{{)_mp1$s_,)2m*{:>},\f{\~2$<@@>+0e|imp}1b!&!}g}*

Just a first pass, this can probably be improved a lot.

Test it here.

Japt, 61 bytes

$while(V<U)T$°,W=Ts ,Tj «Wl o d@1o1-X+Wl)dZ{WjYZ n j} } ©V°;T

Try it online!

It's a shame I haven't implemented loops in Japt yet, otherwise this would be a good bit shorter. Still golfing...