Prime Factorization Help

I am attempting to implement a function to factor large prime numbers, however I am restricted to the particular algorithm given in the comment section above the "findFactor" function. I know better methods are available to factor large numbers, again I am restricted to this algorithm.

With that being said, the program seems to run fine, and even gives correct results for most numbers. However, input like "8" will give 2 , 4, and 2 as the prime factors when it should be 2 2 2. I've been wondering exactly what I have been doing wrong, (most likely something obvious) to get this output for some numbers.

Any help in the right direction would be most appreciative. Thank you for your time.



#include <iostream> //For General I/O.

#include <cmath>    //For sqrt function.

#include <cstring>  //For atoi.

#include <vector>    //For vector ADT.


using namespace std;


/*findFactor Function: (Prime Factorization Algorithm)

    Given an integer "n", find the factors that are less than sqrt(n) by trying all possible

    values. If "k" is an integer between "2" and sqrt(n), k is a factor of "n" if "n%k" is 0.

   

    For each value of "k" in this range we test whether "n%k" is 0. If it is, we have found a

    factor. We store the factor, replace "n" by "n/k" and calculate the new sqrt(n). We then

    continue looking from where we left off. In doing so, we need to use the same value of k

    again in case a power of k divides n.


    When we are done, we have a list of factors of n. Multiply them together to get "m". If

    "m" is not equal to "n", then "n/m" is the remaining prime factor of "n".

*/

vector<int> findFactor(int n, int k){


    vector<int>factor;                                                                    //Vector to store factors.

    vector<int>::iterator it;                                                            //Vector iterator to print etc.

    int i=0,j=0;                                                                        //Counters.

    int m=1;                                                                            //Multiplied value of primes.


    for (k; k<=sqrt((double)n); k++){                                                    //Finds prime factors.

        if (n%k==0){

            factor.push_back(k);

            findFactor(n/k, k);                                                            //Recursive call to findFactor.

        }//end if

    }//end for


    for ( it=factor.begin(); it < factor.end(); it++ )m = m * *it;                        //Multiplies the prime factors.


    if ( m != n ){        

                                                                                        //If, when multiplied m!=n, this finds

        factor.push_back(n/m);                                                            //the last possible prime factor.

        m=m*n/m;

    }//end if


    cout << "Number of primes factors is " << factor.size() << ":" << endl;                //Lists the prime factors.

   

    for ( it=factor.begin(); it < factor.end(); it++ ){

        cout << "Factor " << i << ":" << *it<<endl;

        i++;

    }//end for


    cout << "The prime factors of: " <<endl;                                            //Last output.

    cout << n << " multiply to: " <<endl;

    cout << m <<endl;


    return factor;


};//end findFactor


/*saveValue:

    saveValue saves a given value in a list, the numbers to factor can be arbitrarily large

    therefore this function accomodates for the lack of factors that originally limit the

    size for a 32-bit int list. Limited error checking is used, since most of it is implied

    via the STL for the vector class.

*/

vector<int> saveValue(int n, vector<int> value){    


        value.push_back(n);


return value;


};//end saveValue

   

/*printList:

    This function simply takes the past list of possibly integers entered by the user and

    prints them to the screen for display purposes.

*/

void printList(vector<int> value){


    vector<int>::iterator it;

    int i=0;

    cout << "List:"<<endl;

   

    for ( it=value.begin(); it < value.end(); it++ ){

        cout << i << ":" << *it<<endl;

        i++;

    }//end for


};//end printList


int main(){


    char num[256];

    int n, k=2;

    vector<int> value;


    while(1){


        cout << "Enter number: "<<endl;

        cin >> num;


            if (*num=='q')break;                                                //Exit loop condition.


        n=atoi(num);                                                            //Char input to integer.

                       

        value = saveValue(n, value);                                            //Saves value for list on ints.


        cout << "part1 written by V. Russo"<<endl;

        cout << "Trying to factor: " << n <<endl;

        findFactor(n,k);                                                        //Always start from int 2.


    }//end while


    printList(value);


    return 0;


}//end main