Doprowadzenie liczby do liczby pierwszej w n krokach - rekurencja

Witam wszystkich bardzo serdecznie , od pewnego czasu przeglądam forum ale dopiero teraz postanowiłem się zarejestrować by uzyskać jakąś wskazówke co do mojego kodu.

Problem jest następujący.
Wykonujemy na liczbie operacje : A , B i C. A dodaje do liczby 3, B podwaja liczbe, C zamienia ostatnia cyfre liczby z pierwsza cyfra liczby.

Uzytkownik podaje liczbe a my doprowadzamy ja do liczby pierwszej za pomoca A,B i C i wypisujemy ile kroków było potrzebnych by tego dokonać.

Oto moja próba implementacji :

#include <iostream>
#include <cmath>
using namespace std;

int A (int k)
{
    k+=3;
    return k;
}

int B (int k)
{
    k*=2;
    return k;
}
int C (int k)
{
    int p = k;
    int pierwsza_cyfra;
    int ilosc_cyfr = 0;
    while(p>0)                                        // Funkcję C prawdopodobnie dałoby się zrobić lepiej
    {
        ilosc_cyfr++;
        pierwsza_cyfra = p%10;
        p/=10;
    }
    int ostatnia_cyfra = k%10;
    k = k - ostatnia_cyfra + pierwsza_cyfra - pierwsza_cyfra * pow(10,ilosc_cyfr-1) + ostatnia_cyfra * pow(10,ilosc_cyfr-1);
    return k;
}

bool jest_pierwsza(int k)
{
    if( k == 2) return true;
    if(k%2 == 0)return false;
    int skrt = ceil(sqrt(k));
    for(int i =3 ; i<skrt; i+=2)
    {
        if (k% i == 0) return false;
    }
    return true;
}

int doprowadz_do_pierwszej(int k,int ilosc_krokow )
{
    if(   jest_pierwsza(k)           ) return ilosc_krokow ;
    else
    {
        doprowadz_do_pierwszej( A(k),ilosc_krokow+1  );
        doprowadz_do_pierwszej( B(k),ilosc_krokow+1  );
        doprowadz_do_pierwszej( C(k),ilosc_krokow+1  );
    }
}

//Funkcja doprowadz_do_pierwszej "wpada" w wykonywanie ciagle procedury nr 1 a mimo tego na przykład dla liczby 4
nie wypisuje 1 a po prostu zawiesza się.

int main()
{
    int k;
    while(cin>>k != 0)
    {
        cout<<doprowadz_do_pierwszej(k,0)<<endl;
    }
    return 0;
}

Bardzo chciałbym was zapytać o dwie kwestie :

1. Jak optymalniej napisać funkcję C ? Funkcja działa ale wydaje mi się ona nieco rozlazła, czy istnieje lepszy sposób w C++ na wyciągnięcie z liczby jej pierwszej cyfry?

a) Ma ktoś pomysł dlaczego np dla liczby wejsciowej 4 program zawiesza się zamiast ładnie wypisać 1?
b) Dla liczb ktorych nie da sie sprowadzic do liczby pierwszej poprzez wielokrotne dodawanie 3 - jak ogarnąć parę wywołań rekurencyjnych tak aby "mieszały się ze sobą " a nie na przyklad ciagle byla wywolywana jedna funkcja.

Będę wdzięczny za każdą nawet drobną i ironiczną wskazówkę jak również za dłuższe wyjaśnienie sprawy.

Z góry dziękuje i pozdrawiam.

w int doprowadz_do_pierwszej(int k,int ilosc_krokow )

jest błąd,

zauważ, że po wyjściu z rekurencji nie masz return, poza ifem, załatw sobie nowszy kompilator, warning brzmi
C:\c++qt\abc\main.cpp:58: warning: control reaches end of non-void function [-Wreturn-type] } ^

jednym słowem masz UB -> Twoje wyniki lecą w kosmos

Jak duże mogą być te liczby?

Moje podejście jest dynamiczne, więc wymaga podania zasięgu szukania (więc nie ma gwarantowanych 1. najlepszej możliwej odpowiedzi 2. jakiejkolwiek odpowiedzi)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

std::vector<uint8_t> constructSieve(size_t size)
{
    std::vector<uint8_t> sieve(size, true);
    sieve[0] = sieve[1] = false;
    for(size_t i = 2; i < size; ++i)
    {
        for(size_t j = i + i; j < size; j += i)
        {
            sieve[j] = false;
        }
    }
    return sieve;
}

size_t switchDigits(size_t number)
{
    size_t originalNumber = number;
    size_t mostSig;
    size_t leastSig;
    size_t lastDigitPlace = 1;
    leastSig = number%10;

    while(number >= 10)
    {
        lastDigitPlace *= 10;
        number /= 10;
    }
    mostSig = number;
    if(mostSig == leastSig) return originalNumber;
    originalNumber -= mostSig * lastDigitPlace;
    originalNumber += mostSig;
    originalNumber -= leastSig;
    originalNumber += leastSig * lastDigitPlace;
    return originalNumber;
}

size_t movesToGetPrimeFrom(const std::vector<uint8_t>& sieve, size_t startingNumber)
{
    if(sieve[startingNumber]) return 0;
    size_t size = sieve.size();
    size_t minMovesForPrime = 0x7FFFFFFF;
    std::vector<int> movesToGet(size+1, 0x7FFFFFFF);
    movesToGet[startingNumber] = 0;
    for(size_t i = startingNumber+1; i <= size; ++i)
    {
        size_t movesToGetFromEarlierNumber[3] = {0x7FFFFFFF,0x7FFFFFFF,0x7FFFFFFF};
        if(i-3>=startingNumber) movesToGetFromEarlierNumber[0] = movesToGet[i-3];
        if(i/2>=startingNumber && !(i&1)) movesToGetFromEarlierNumber[1] = movesToGet[i/2];
        size_t switched = switchDigits(i);
        if(switched>=startingNumber && switched != i) movesToGetFromEarlierNumber[2] = movesToGet[switched];

        movesToGet[i] = min(min(movesToGetFromEarlierNumber[0], movesToGetFromEarlierNumber[1]),movesToGetFromEarlierNumber[2])+1;
        if(sieve[i] && movesToGet[i] < minMovesForPrime) minMovesForPrime = movesToGet[i];
    }
    return minMovesForPrime;
}

int main()
{
    std::vector<uint8_t> sieve = constructSieve(1000000);
    std::cout << movesToGetPrimeFrom(sieve, 4);
    return 0;
}

I jeszcze mała uwaga
Żadnej liczby postaci 3*n nie da się doprowadzić do liczby pierwszej przy użyciu tych trzech funkcji.
Nie wiem czy jeszcze jakichś nie można czy tylko takich.