The Eratosthenes Shuffle
Mathematica, 61 bytes
#[[SortBy[Range@Length@#,FactorInteger[#][[1,1]]PrimeQ@#&]]]&
Unnamed function taking a list of characters as input and returning a list of characters.
FactorInteger[#][[1,1]]
yields the smallest prime factor of #
(and returns 1
if #
equals 1
). Therefore FactorInteger[#][[1,1]]PrimeQ@#
yields a strange expression: [#
's smallest prime factor] False
if #
is not prime, and # True
if #
is prime (these are unevaluated products of a number and a boolean).
Range@Length@#
yields a list of the numbers up to the length of the input. Then SortBy
sorts those numbers by the funny function described above. Mathematica is really type-sensitive in many ways, but cheerfully mixes them in other ways: expressions of the form [number] False
are alphabetically sorted before expressions of the form [number] True
, while ties are broken by sorting the numbers numerically. That produces exactly the permutation we want here, and #[[...]]
permutes the characters of the input accordingly.
Jelly, 10 bytes
JÆfṂ$ÞÆPÞị
TryItOnline
How?
JÆfṂ$ÞÆPÞị - Main link: theString
J - range(length), the 1-based indexes of theString
Þ - sort these by
$ - last two links as a monad
Æf - prime factorization array (e.g. 20 -> [2,2,5])
Ṃ - minimum
Þ - sort these by
ÆP - isPrime, i.e. move all the primes to the right
ị - index into theString
C, 164 bytes
This takes input as the first command parameter and prints back to stdout. As we process each character, we clear it, allowing the final pass.
#define p putchar
main(c,s,i,j,t)char**s,*t;{c=strlen(t=s[1]);p(*t);for(;j++<c;)if(t[j])for(i=2*j+1;i<=c;i+=j+1)!t[i]?:p(t[i]),t[i]=0;for(j=0;j++<c;)!*++t?:p(*t);}