[Question]
  [
The "prime frog" is a strange animal that jumps between integers, until it arrives on 3 or 19...
---
Your program should accept an integer `n` as input and output the result of the below algorithm (`3` or `19`).
For a given integer `n >= 2`:
1. Let `f` be the position of the frog. It is initially set to `n`
2. if `f = 3` or `f = 19` : the frog stops jumping - halt the program and output `f`.
3. if `f` is prime : the frog jumps to the position `2√óf-1`. Go back to step 2.
4. if `f` is composite : let `d` be `f`'s biggest prime divisor. The frog jumps to the position `f-d`. Go back to step 2.
**Examples:**
An example with `n = 5`:
```
5 > 9 > 6 > 3 stop
```
The program should output `3`.
Another example with `n = 23`:
```
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
```
Again, the program should output `3`.
**Test cases:**
```
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
```
You can assume `1 < n < 1000000` (I have checked the program ends for these values).
  
[Answer]
# [Python 2](https://docs.python.org/2/), ~~101~~ ~~93~~ ~~92~~ ~~90~~ ~~88~~ ~~87~~ 85 bytes
```
import sympy
n=input()
while~16&n-3:m=max(sympy.factorint(n));n-=[1-n,m][m<n]
print n
```
[Try it online!](https://tio.run/##HY1BDoMgFET3/xTERSNNbaSSKm05iXFhKI0k8iGWprLp1an4kpnNTGZ8DJPDS1LuqWVRFMlY75ZA3tH6CCgN@k8oKXwnM@sfux6wam5W2nEt98r5NargFoOhRErvWMmeVXiyQ28fOIDPCcG0LQPoVSuSj45dYjW0HAQHzloQgm3qms0ywOqdPw "Python 2 ‚Äì Try It Online")
[Answer]
# C (gcc), ~~¬†87¬†~~ 65 bytes
```
i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);n=~16&n-3?f(n-k?:n+n-1):n;}
```
[Try it online!](https://tio.run/##dctBCsIwEAXQfU8RCpUMdsDQYm2H2Iu4kUhkCB2luCv16jF1q5nd/@@Pw7tzMXIdyGuBxT9mzVaIz4ZgC8EyhQqRCUjs2xx3gs2YthjGQfaCBgahNbK81HRl0VAshUr3nFPldVndLlLWymtzAKD/1LVZ6vPUmi7/1ptfS6K@dmo2XOMH)
**Explanation:**
```
i,k;
f(n)
{
    for (i=n; i>1;)              // Loop until `k` is prime (the largest positive
                                 // `i` inequal to `k` that divides `k` is 1).
        for (k=i; k%--i;);       // Find the largest factor `k`
    n =                          // Returning like this is undefined behaviour,
                                 // but happens to work with gcc. This can be
                                 // replaced with `return` at the cost of 4 bytes.
        ~16&n-3                  // If `n` is 3 or 19, this expression equals 0 and
                                 // the algorithm halts. Otherwise the function
                                 // calls itself to perform the next iteration.
        ? f(n-k ?: n+n-1)        // If `n-k` is non-zero, n is not prime.
                                 // In this case call `f` with the value of `n-k`.
                                 // (Omitting the second `n-k` between `?` and `:`
                                 // is a gcc extension)
                                 // Otherwise call `f` with `2*n-1`.
        : n;                     // All done, `n` is returned.
}
```
**Portable version (72 bytes):**
```
i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);return~16&n-3?f(n-k?n-k:n+n-1):n;}
```
[Try it online!](https://tio.run/##dcvBCoJAEAbgu0@xCMYOudCgZDqYL9JFrI1ha4rFTmKvvq1dy4E5/PP9M5jh1ss1BM4dWS0w2YfX3ArxEQmW4FomlxnDBOQv48vLG/cbMUUX@8Z1cRvZikFohObAMqp7z6IhmRIV5@njyeo0O58kzZXVuAOg/1SVq1SvU4nV@luNvxZFfe1QLDiHDw)
**With more appropriate variable names:**
```
f,r;o(g){for(f=g;f>1;)for(r=f;r%--f;);g=~16&g-3?o(g-r?:g+g-1):g;}
```
[Try it online!](https://tio.run/##dctBCoMwEAXQvacIgiVDDTQotTqkXqSbkjKDixoZuhN79TR222Z2/78/3rD3MVItGDTDSkE0OUa6WoQ9iCOUyhhCQHZvez6waca0NTIOfGRjYWDc4jS/1PM@zRqKtVDpFkkV6bJ63OayVkHbEwD@p67NUp@n1nb5t97@WhL1tUuz4xY/)
[Answer]
## [Retina](https://github.com/m-ender/retina), ~~63~~ 62 bytes
*Thanks to Neil for saving 1 byte.*
```
{`^(11+)(?<!^\2+(11+))(?=\1+$)
^(?!(11+)\1+$|111$|1{19}$)1
$_
```
[Try it online!](https://tio.run/##HcixCoAgAEXR/f2FYKAJ0QtBhKKxnxCzoaGlIdqqb7dyuXDusZ7bvuRKpcZA1vlKUZFGq7EXMXSm4NMQaKQGohpFeb9vkl8u@kdqQs5ZTwnMbOEsvIWlg/d8AQ "Retina ‚Äì Try It Online")
Input and output in unary (the test suite uses decimal for convenience). This solution gets incredibly slow for larger inputs. The `9983` test case times out on TIO.
### Explanation
Due to the `{`, both stages of the program are simply run in a loop until they no longer affect the string. We alternate between a stage processing composites and a stage processing primes. That lets us avoid an actual conditional (which doesn't really exist in Retina). If the current value is the wrong kind for the stage, the stage simply does nothing.
```
^(11+)(?<!^\2+(11+))(?=\1+$)
```
This processes composites. We match a potential divisor with `(11+)`, but then we check that it's not composite with `(?<!^\2+(11+))`, so we only consider prime factors. Due to the greediness of `+`, this prioritise the largest factor. Then we check that this potential divisor is an *actual* divisor by trying to match the rest of the string with repetitions of it, `(?=\1+$)`. This divisor is simply removed from the string, which is how you subtract something in unary.
```
^(?!(11+)\1+$|111$|1{19}$)1
$_
```
This processes primes, except **3** and **19**. The negative lookahead makes sure that the input is not composite, not **3** and not **19**. Then we match a single `1` and replace it with the entire string. This is a unary form of computing **n - 1 + n**, which of course is **2n-1**.
Once we hit **3** or **19**, neither stage can match the string and it will no longer be changed.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 bytes
```
_√Üf·πÇo·∏§‚Äô$¬µ√ê·∏∂·πÇ
```
[Try it online!](https://tio.run/##y0rNyan8/z/@cFvaw51N@Q93LHnUMFPl0NbDEx7u2AYU@X90z@H2R01r3P//NzTQUTA30VGwNNRRMDE0BzJALEtLC2MA "Jelly ‚Äì Try It Online")
### How it works
```
_√Üf·πÇo·∏§‚Äô$¬µ√ê·∏∂·πÇ  Maink link. Argument: n
        ¬µ     Combine the links to the left into a chain.
         √ê·∏∂   Repeatedly call the chain monadically until the results are no longer
              unique. Yield the loop, i.e., the first occurrence of the first
              repeated integer, up to and excluding the repetition.
              Let's call the argument of the chain k.
_√Üf             Subtract all prime factors of k from k.
   ·πÇ            Take the minimum of the differences. This yields 0 iff k is prime.
     ·∏§‚Äô$        Compute 2k-1.
    o           Take the logical OR of the results.
              The result is now a rotation of either [3, 5, 9, 6] or
              [19, 37, 73, 145, 116, 87, 58, 29, 57, 38].
          ·πÇ   Take the minimum, yielding either 3 or 19.
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 15 bytes
```
Œ©‚Ç¨p57¬ß|o‚ÜêD·π†-o‚Üíp
```
[Try it online!](https://tio.run/##yygtzv6vkKtR/KipsUjz0Lb/51Y@alpTYGp@aHlN/qO2CS4Pdy7QBTImFfz//9/QgMvchMvShMvE0JzL0tIQiC2MAQ "Husk ‚Äì Try It Online")
## Explanation
```
Œ©‚Ç¨p57¬ß|o‚ÜêD·π†-o‚Üíp  Implicit input n.
Œ©                Do this to n until
 ‚Ç¨p57            you get a prime factor of 57 (which are 3 and 19):
            o‚Üíp   Take last element of the prime factors of n
          ·π†-      and subtract it from n,
     ¬ß|           or if this gives 0 (so n is prime),
       o‚ÜêD        double and decrement n.
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 65 ~~66~~ ~~68~~ bytes
```
#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
```
* *-1 bytes, thanks to Misha Lavrov!*
* *-2 bytes, thanks to Martin!*
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7X1lfXy8zXt86U9HWWE0NSBpaWtl5pkUHFGXmpgY6ZOoYZeoa6mTqKqs5OPgkFpc4uCUml@QXeeaVpKanFjlkxqr9ByrNK4lOizY0iI3lgnHMTZA4lsgcE0NzZClLQxSehXFs7H8A "Wolfram Language (Mathematica) ‚Äì Try It Online")
Inspired by [the tip](https://codegolf.stackexchange.com/a/106652/59292). Basically, it just recreates the algorithm.
`//.` is `RepeatedReplace` and `/;` is `Condition`. So, the code will replace `i_` (a single quantity) with `If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]`, until `i!=3&&!=19` evaluates `True`.
Benchmark:
[![benchmark](https://i.stack.imgur.com/tyb5wm.png)](https://i.stack.imgur.com/tyb5wm.png)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~19~~ ~~18~~ 17 bytes
```
[√ê∆µŒ∑fs√•#pi¬∑<√´DfŒ∏-
```
[Try it online!](https://tio.run/##ASQA2/8wNWFiMWX//1vDkMa1zrdmc8OlI3Bpwrc8w6tEZs64Lf//MjM "05AB1E ‚Äì Try It Online")
**Explanation**
```
[      #            # loop until
 √ê   s√•             # a copy of the current value is contained in
  ∆µŒ∑f               # the unique prime factors of 171
        pi          # if the current value is prime
          ¬∑<        # double and decrement
            √´   -   # else subtract
             DfŒ∏    # the largest prime factor of a copy of the current value
```
[Answer]
# JavaScript (ES6), ~~73~~ ~~71~~ 69 bytes
```
f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38
```
### Test cases
```
f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38
console.log('10   -> ' + f(10))   // 3
console.log('74   -> ' + f(74))   // 19
console.log('94   -> ' + f(94))   // 3
console.log('417  -> ' + f(417))  // 3
console.log('991  -> ' + f(991))  // 19
console.log('9983 -> ' + f(9983)) // 19
```
### Formatted and commented
```
f = n =>                 // given n
  57 % n ?               // if n is neither 3, 19 or 57 (and assuming that n is > 1):
    f(                   //   do a recursive call to f() with:
      n -                //     n minus
      (g = (k, d = 1) => //     the result of the recursive function g():
        ++d < k ?        //       increment d; if d is less than k:
          k % d ?        //         if d is not a divisor of k:
            g(k, d)      //           recursive call to g() with k and d unchanged
          :              //         else:
            g(k / d)     //           recursive call to g() with k = k / d, d = 1
        :                //       else, d is now the highest prime divisor of n:
          d < n ?        //         if d is less than n:
            d            //           n is composite: return d, which results in f(n - d)
          :              //         else:
            1 - n        //           n is prime: return 1 - n, which results in f(2n - 1)
      )(n)               //     initial call to g()
    )                    //   end of recursive call to f()
  :                      // else:
    n % 38               //   return n % 38 (gives 19 as expected if n = 57)
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~23~~ 19 bytes
*-4 bytes from [miles](https://codegolf.stackexchange.com/users/6710/miles).* Still longer than 05AB1E, though.
```
·∏§‚Äô$_√Üf$√ÜP?·π™¬µ·∏ü3,19$¬ø
```
[Try it online!](https://tio.run/##ASsA1P9qZWxsef//4bik4oCZJF/DhmYkw4ZQP@G5qsK14bifMywxOSTCv////zIz)
[Answer]
# [Python 2](https://docs.python.org/2/), ~~110~~ ~~105~~ ~~103~~ 101 bytes
*-2 bytes thanks to @Lynn*
```
f=lambda n,i=2,k=0:i/n and(n*(n&~16==3)or f((2*i-1,k-i)[k>0]))or n%i and f(n,i+1,k)or f(n/i,2,k or n)
```
[Try it online!](https://tio.run/##JY3PDoIwDMbve4peNJtO2SYRIZkvYjjgv9gghWzzwMVXxy42@dqm/fXrNKfXSG7BYRpDgjhHwdrHRwqP2ydEHOmNAybpDIdanv7dDdd7B6TRO91702BB0NFd0kbS@muP3h/UGOAppdvgzup@h@rSn02r8phWmGles8OWt3@WCtRsB5ngL1wQkOBijYaq1FCzSltxU9ucToe2EQBTQEp8jmqxRlSlqEvBmGBKZOgH "Python 2 ‚Äì Try It Online")
---
# [Python 2](https://docs.python.org/2/), ~~116~~ ~~112~~ 105 bytes
```
f=lambda n,i=2:i/n*i or n%i and f(n,i+1)or f(n/i)
n=input()
while~16&n-3:n=[2*n-1,n-f(n)][f(n)<n]
print n
```
[Try it online!](https://tio.run/##FY3BCoMwGIPv/1MUYcM6xVVFp6xPIh6cVvzBpSKObZe9elcPCSEJfOt3ny0yN9jR6CAI3KSX/vkYe4GYddZwioiF3QROLHqMYgr9cFHSVz6mLAmasb72UNJ75sX8VHlGkjfQbRYhUTESf5Rde/gdHa0bYxdwnkbmYwZxsKPSqStVBdUFFaqiulZet/wP "Python 2 ‚Äì Try It Online")
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~22~~ 21 bytes
*Thanks to [@Giuseppe](https://codegolf.stackexchange.com/users/67312/giuseppe) for removing 1 byte!*
```
`tZp?Eq}tYfX>-]tI19h-
```
[Try it online!](https://tio.run/##y00syfn/P6EkqsDetbC2JDItwk43tsTT0DJD9/9/S0sLYwA) Or [verify all test cases](https://tio.run/##y00syfmf8D@hJKrA3rWwtiQyLcJON7bE09AyQ/d/rEvIf0MDLnMTLksTLhNDcy5LS0MgtjAGAA).
### Explanation
```
`           % Do...while
  t         %   Duplicate. Takes (implicit) input the first time
  Zp        %   Is it prime? 
  ?         %   If so
    Eq      %     Times 2, minus 1
  }         %   Else
    t       %     Duplicate
    YfX>-   %     Prime divisors, maximum, subtract
  ]         %   End
  t         %   Duplicate
  I19h      %   Push array [3 19]
  -         %   Subtract, element-wise. The result is truthy if and only if
            %   it doesn't contain any zero
            % End (implicit). Next iteraton if top of the stack is truthy
            % Display (implicit)
```
[Answer]
# Haskell - 154 bytes
```
f 3=3
f 19=19
f n
 |(c==[1])=f$2*n-1
 |True=f$n-head c
 where c=z n;v b=reverse[x|x<-[1..(b-1)],b`rem`x==0];z j=case v j of[1]->[1];s->filter((==[1]).v)$s
```
Probably missing some golf tricks here, this is my first attempt at haskell golf.
[Answer]
# [Neim](https://github.com/okx-code/Neim), ~~17~~ 16 bytes
```
ÕªYùêèùïö√∑DùêåŒû·ö´<#Dùêèùê†ùïä
```
Explanation:
```
Õª                   Start infinite loop
 D                  Duplicate
  Y                 Push 57
   ùêè                Prime factors: [3 19]
     ùïö              If the second-to-top of stack is in the list
      √∑             Break the loop
       D            Duplicate
        ùêåŒû·ö´<       If prime, double and decrement
            #Dùêèùê†ùïä   Otherwise, subtract the largest prime factor
```
[Try it online!](https://tio.run/##y0vNzP3//@xul8gPcyf0f5g7ddbh7S5AZs@5eQ9nrbZRdoEIT1gAlOr6/9/S0sIYAA "Neim ‚Äì Try It Online")
[Answer]
# [R](https://www.r-project.org/) + [numbers](https://cran.r-project.org/web/packages/numbers/numbers.pdf), ~~102~~ 99 bytes
```
function(n){while(!n%in%c(3,19))n="if"(isPrime(n),2*n-1,n-max(primeFactors(n)))
n}
library(numbers)
```
[Try it online!](https://tio.run/##FYpBCsIwEADv/YWFwq5swNhCDejVs19IQ4ML7TYkLVrEt8d4mMvMxOyvKvtN3MqLgODn9eRphIM0LI2DlrRBlFvNvgZOj8jzWC46H0VpEjXbN4S/vFu3LjGVhljJt5p4iDbuINs8jDFhTjaEaQcH@kR9R6ajTvdkjC5cWiSP@Qc "R ‚Äì Try It Online")
R isn't known for short built-ins, and even the packages follow suit!
[Answer]
# Java 8, ~~140~~ ~~135~~ ~~134~~ 94 bytes
```
n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;t/=m=f);return n%38;}
```
-5 bytes converting recursive Java 7 method to Java 8 lambda with loop.  
-1 byte implicit thanks to [*@Arnauld*'s JavaScript answer](https://codegolf.stackexchange.com/a/145759/52210) by changing `n!=3&n!=19` and `return n;` to `57%n>0` and `return n%38;`.  
~~I think it should be possible to somehow combine the two loops and check if `n` is a prime, and get it's largest prime factor at the same time, but I can't figure it out (yet). So this will be the initial version for now.~~  
-40 whopping bytes thanks to @Nevay, by doing what I couldn't do: combining the loops to check for primes and largest prime factor at once.
**Explanation:**
[Try it here](https://tio.run/##dZLNboJAEMfvPsWExAQKWCkapevaJ6gXj7WH7brbYGEgMJg2hmenC0pqsQWyyfzmk//sQRyFn@UKD/uPRiaiLOFZxHgaAcRIqtBCKti0ZgdA2u2JDjOkHpmjJEGxhA0gcGjQX590VnRB2iMv5VM2X4xxPWXI9RqfHu7QDx7RT502jDh6mgdMu@6KWIcYjfUqYHTPU64dViiqCgQch0tWN6ztmFdviel4aXzM4j2kZmR7S0WM7y@vIJzzvNuvklQ6ySqa5MZFCdpWjHlFO/Oqz1xJUvsdCUmVSFpGqiQoKylVWeoqsbq//LPOxdMm2HMPwms7mA7AQzgAi5kHQXRNotkgZBYsBiSKgpusaBnesvbpc2uAUfeZwY@C1C/VuvhunYXXLbfXxPnZ91kcs1qcSBuL/xXBwrVaDS23r9Lb5xK9Zfduzs8O53KX6uYb) (executes even `999999` in under 1 second).
```
n->{                  // Method with integer as both parameter and return-type
  for(int f,          //  Flag-integer
          t,          //  Temp-integer
          m=1;        //  Max prime factor integer, starting at 0
      57%n>0;         //  Loop (1) as long as `n` is not 3, not 19 and not 57:
      n=f>n?          //    After every iteration: if `f` is larger than `n`:
         2*n-1        //     Change `n` to `2*n-1`
        :             //    Else:
         n-m)         //     Change `n` to `n-m`
    for(t=n,          //   Reset `t` to `n`
        f=1;          //   Reset `f` to 1
        f++<t;)       //   Inner loop (2) from 2 to `t` (inclusive)
      for(;t%f<1;     //    Inner loop (3) as long as `t` is divisible by `f`
        t/=m=f;       //     Set `m` to `f`, and set `t` to `t/f`
      );              //    End of inner loop (3)
                      //   End of inner loop (2) (implicit / single-line body)
                      //  End of loop (1) (implicit / single-line body)
  return n%38;        //  Return `n%38`, which is now either 3 or 19
}                     // End of method
```
[Answer]
# Bash, 73 bytes
```
((57%$1))&&$0 $[(x=$1-`factor $1|sed 's/.* //'`)?x:2*$1-1]||echo $[$1%38]
```
[Try it online!](https://tio.run/##S0oszvifb6uUBKQVVAyUFJQV0jIrFNLyi4A8hZJ8hfL8omyF/DyFEE///xoapuaqKoaammpqKvkKKtEaFbYqhroJaYnJJSD1hjXFqSkK6sX6eloK@vrqCZr2FVZGWkAVhrE1NanJGSAtKoaqxhax////t7S0MAYA) Modified slightly to work on TIO.
Recursively calls its own script file using `$0`, ~~which does not work in TIO because it must be ran as `./filename.sh`~~. Accepts input as command-line argument.
Uses the same modulus trick as [@Arnauld's JS answer](https://codegolf.stackexchange.com/a/145759/69583).
## Test Cases
```
$ for t in 5 23 10 74 94 417 991 9983;{ echo -n "$t -> "; ./prime-frog.sh $t; }
5 -> 3
23 -> 3
10 -> 3
74 -> 19
94 -> 3
417 -> 3
991 -> 19
9983 -> 19
```
[Answer]
# [Python 3](https://docs.python.org/3/), 97 bytes
```
f=lambda n:n*(n&-17==3)or f(n-max(k*all(n%k<k%j for j in range(2,k))for k in range(n+1))or 2*n-1)
```
[Try it online!](https://tio.run/##RY7BDoIwDIbP@hS9IC0O44AEWZzvMqMoDAohO2gIzz63k4f@ab4vbf75694Tl963ejDj/WGAFWfIh1zWWpc0LdAi56P5oM3MMCAn9mqTHtpgeugYFsOvJxbCEkVm/4yPkuKDIuNcko@Wo5VnAXUloAlTyTosjYxxKdV@Ny8dO0xXVW2gb7CqYktP4XQ0DlnEMkTkfw "Python 3 ‚Äì Try It Online")
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 19 bytes
```
.W!/P57H?P_ZtyZ-ZeP
```
**[Verify all the test cases!](https://pyth.herokuapp.com/?code=.W%21%2FP57H%3FP_ZtyZ-ZeP&test_suite=1&test_suite_input=10%0A74%0A94%0A417%0A991%0A9983&debug=0)**
The [Husk answer](https://codegolf.stackexchange.com/a/145755/59487) inspired me to save 2 bytes (`,3 19` to `P57`).
## How this works
```
.W!/P57H?P_ZtyZ-ZeP  - Full program.
.W                   - Functional while. While A(value) is truthy, value = B(value). Returns the last value.
    P57              - The prime factors of 57 ([3, 19]).
   /   H             - Count the occurences of the current value.
  !                  - Logical NOT. 0 -> Truthy, anything else -> Falsy.
        ?P_Z         - If the current value is prime, then:
            tyZ        - Double the current value, decrement.
               -ZeP    - Else, Subtract the maximal prime factor of the current value from itself.
                     - Print implicitly.
```
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), ~~150~~ 126 bytes
```
for($n="$args";57%$n){$a=$n;$d=for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}};if($n-in$d){$n+=$n-1}else{$n-=$d[-1]}}$n%38
```
[Try it online!](https://tio.run/##LcxBCsMgFATQszSMoAQpNpQmyD9J6ULQpIL8FC10ETy7ldLlzDzmtX9CLs@QUmvrniWYBri8lcFebwKsDjgCW3j6zZEuFk5vb6OOuMqThBOIqrPY@zMh1pBK6HEca7WdgHVk@C547E/a/AFrgr9r86gVLKa5tbYs8/QF "PowerShell ‚Äì Try It Online") (warning: slow for bigger numbers)
Iterative method. PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on [Prime Factors Buddies](https://codegolf.stackexchange.com/a/94323/42963).
First is our `for` loop. The setup sets `$n` to be the input value, and the conditional keeps the loop going so long as `57%$n` is non-zero (thanks to [Arnauld](https://codegolf.stackexchange.com/a/145759/42963) for that trick). Inside the loop we first get a list of prime factors of `$a` (set to `$n`). This is the code borrowed from Prime Factors Buddies. If the input `$a` is already prime, this will return just `$a` (important later). That (potentially just `$a`) gets stored into `$d`.
Next is an `if`/`else` conditional. For the `if` part, we check whether `$n` is `-in` `$d`. If it is, that means that `$n` is prime, so we take `$n=2*$n-1` or `$n+=$n-1`. Otherwise, it's composite, so we need to find the largest prime factor. That means we need to take the last one `[-1]` of `$d` and subtract that from `$n` with `$n-=`. This works because we're looping up from `2` and thus the last element of `$d` is already going to be the largest.
Once we're done looping, we just place `$n%38` (again, thanks Arnauld) on the pipeline and output is implicit.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~113~~ ~~90~~ 59 [bytes](https://codegolf.meta.stackexchange.com/questions/9428/when-can-apl-characters-be-counted-as-1-byte-each/9429#9429)
```
‚éïCY 'dfns'
g‚Üê{1pco ‚çµ:f(2√ó‚çµ)-1‚ãÑf‚çµ-‚äÉ‚åΩ3pco ‚çµ}
f‚Üê{‚çµ‚àä3 19:‚çµ‚ãÑg ‚çµ}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT/8PBI/6pjpHKqinpOUVq3OlP2qbUG1YkJyv8Kh3q1WahtHh6UCGpq7ho@6WNCBL91FX86OevcZQFbVcaSANQNajji5jBUNLKxCzuyUdLAkA "APL (Dyalog Unicode) ‚Äì Try It Online")
~~TIO works with values up to ~3200. Tested on my PC for the last test case. To test on TIO, just add `f value` to the bottom of the code.~~
Doesn't apply anymore, thanks to @Ad√°m for pointing out that my primality checking algorithm was really bad and supplying me with a replacement; also for the 23 byte save.
Edited to fix byte count.
### How it works
```
‚éïCY 'dfns'                      # Imports every Defined Function, which is shorter than importing just the function I used (pco).
g‚Üê{1pco ‚çµ:f(2√ó‚çµ)-1‚ãÑf‚çµ-‚äÉ‚åΩ3pco ‚çµ} 
g‚Üê                              # define g as
   1pco ‚çµ:                      # if the argument ‚çµ is prime
          f(2√ó‚çµ)-1              # Call f over 2√ó‚çµ-1
                  ‚ãÑf            # else, call f over
                    ‚äÉ           # the first element of the
                      3pco ‚çµ    # list of prime factors of ‚çµ
                     ‚åΩ          # reversed
f‚Üê{‚çµ‚àä3 19:‚çµ‚ãÑg ‚çµ}
f‚Üê                              # Define f as
   ‚çµ     :                      # if the argument ‚çµ
    ‚àä                           # is in
     3 19                       # the list [3, 19]
          ‚çµ                     # return the argument ‚çµ
           ‚ãÑ                    # else
            g ‚çµ                 # call g over the argument ‚çµ
```
[Answer]
# Axiom, 93 bytes
```
h(n)==(repeat(n=3 or n=19 or n<2=>break;prime? n=>(n:=2*n-1);n:=n-last(factors(n)).factor);n)
```
test:
```
(4) -> [[i,h(i)] for i in [10,74,94,417,991,9983]]
   (4)  [[10,3],[74,19],[94,3],[417,3],[991,19],[9983,19]]
                                                  Type: List List Integer
```
There would be 68 bytes function
```
q x==(n<4=>3;n=19=>n;prime? n=>q(2*n-1);q(n-last(factors n).factor))
```
but for n=57991 (if I remember well) it goes out the stack space reserved.
[Answer]
# [Python 2](https://docs.python.org/2/), 93 bytes
Port from [TFeld's answer](https://codegolf.stackexchange.com/a/145748/66418) without external libs.
```
n=input()
while~16&n-3:
 f=n;i=2
 while i<f:
	if f%i:i+=1
	else:f/=i
 n-=[1-n,f][f<n]
print n
```
[Try it online!](https://tio.run/##JU67CsJAEKyzX7EEFEWDnglqTq@MrY1dsJC4hwuyOS4nxsZfj6cWU8wM83CvcGtlNTTtlUyapoMYFvcIkyk8b3ynt1qPJcs1oDWyY7MC/OnIe6shYYt2xJpnRkFC9460XRgGlMzUKpO5Pdd2L2dwniWgDHEBIPhXjP5rTv5BkSTUU4PfE0B9Qy5gdTxU3rc@mu7SdYNa5rApoCygUBsoSxWxzT8 "Python 2 ‚Äì Try It Online")
]