質因數分解

質因數分解

#include <iostream>

#include <vector>

using namespace std;

vector<int> PrimeFactor(int num); //GET Prime Factor of num.

vector<int> GeneratePrime(int n); //Generate prime numbers less than num

bool CheckPrime(int nCheckNum, int nPrimeArrayNowNum, vector<int> *vecPrime);//Is the number nCheckNum a prime?

int GetPrime(int nIndex, vector<int> *vecPrime); //Get Prime

int main()

{

vector<int> vecPrimeFactors = PrimeFactor(20); //GET Prime Factor of num.

vector<int>::iterator it;

for(it = vecPrimeFactors.begin() ; it != vecPrimeFactors.end() ; it++)

{

printf("%d, ", *it);

}

printf("\n");

system("pause");

return 0;

}

vector<int> GeneratePrime(int n) //Generate prime numbers less than num

{

vector<int> vecPrime;

vecPrime.clear();

vecPrime.push_back(2);

int nPrimeArrayNowNum = 1;

for(int i = 3 ; i < n ; i++)

{

if(CheckPrime(i, nPrimeArrayNowNum, &vecPrime))

{

vecPrime.push_back(i);

nPrimeArrayNowNum++;

        }

}

return vecPrime;

}

bool CheckPrime(int nCheckNum, int nPrimeArrayNowNum, vector<int> *vecPrime)//Is the number nCheckNum a prime?

{

  for(int i = 0 ; i < nPrimeArrayNowNum ; i++)

{

if(GetPrime(i, vecPrime) == 0)

return false;

if(nCheckNum % GetPrime(i, vecPrime) == 0)

return false;

}

return true;

}

int GetPrime(int nIndex, vector<int> *vecPrime)//Get Prime

{

if(nIndex < 0 || nIndex >= (int)vecPrime->size())

return 0;

return (*vecPrime)[nIndex];

}

int Divisible(int n1, vector<int> *vecPrime)

{

vector<int>::iterator it;

for(it = vecPrime->begin() ; it != vecPrime->end() ; it++)

{

if(n1 % *it == 0)

return *it;

}

return -1;

}

vector<int> PrimeFactor(int num)

{

vector<int> vecPrimes = GeneratePrime(num); //Generate prime numbers less than num

vector<int> vecPrimeFactor;

vecPrimeFactor.clear();

int divisor = num;

int prime;

int quotient;

while(1)

{

prime = Divisible(divisor, &vecPrimes);

if(prime != -1)

vecPrimeFactor.push_back(prime);

quotient = divisor/prime;

if(quotient == 1)

break;

divisor = quotient;

}

return vecPrimeFactor;

}