The Eratosthenes Shuffle

Question

Challenge

Write a function or program that accepts a line of input, performs a very specific and oddly familiar shuffle on its characters, and outputs the result.

The required shuffling can be described using the following algorithm:

1. Label each character in the input with a 1 based index.
2. Write character number 1 as output.
3. Starting with character number 2, write every other character to the output in order, excluding character 2 itself. In other words, write characters 4, 6, 8, 10, and so on as output.
4. Starting with the next character number n not yet written as output, write every nth character to the output, excluding character n itself, and excluding any other character (by numeric label) you may have already written to the output.
5. Repeat step 4 as long it continues to add new characters to the output.
6. Write the remaining characters to output, in order.

Example

1. Label the characters.

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R

2. Write the first character to output:

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
O

3. Write every other character starting with 2, excluding 2.

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
O O A' EUYCRE

4. The next character not yet written is character number 3; write every 3rd character starting with 3, but excluding character 3 itself, and any character already written.

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
O O A' EUYCREYB R

5. Repeat step 4 using the next character, character 5.

4. The next character not yet written is character number 5; write every 5th character starting with 5, but excluding character 5 itself, and any character already written. (This amounts to just character 25).

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
O O A' EUYCREYB RN

5. The next character is 7; but 14, 21 have already been written, so no more characters would be output if we repeat step 4. Thus, we're done with 5.

6. Write the remaining characters out in order.

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
O O A' EUYCREYB RNLDDCKSATO

Rules

Input and output may be via standard input/standard output, strings, or arrays of characters.

If reading in as standard input you may at your convenience assume there's a trailing newline, or that the entire input contains the line. Newline characters do not participate in the shuffle.

Likewise, at your convenience, your output may either have a trailing newline or not.

Standard loopholes are disallowed.

This is a code golf competition. Smallest code in bytes wins.

Test Cases

123456789ABCDEF -> 1468ACE9F2357BD

OLD DOC YAK'S BEAUTY CORNER -> O O A' EUYCREYB RNLDDCKSATO

Blue boxes use a 2600hz tone to convince telephone switches that use in-band signalling that the caller is actually a telephone operator.
->
Bebxsuea20h oet ovnetlpoesice htuei-adsgaln httecle satal  eehn prtre 0ncce ha nng aiuapootnt ihyon atallu o s 6z oi ehwstsnbilt lr clee.

Answer 1

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.

Answer 2

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

Answer 3

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);}