素数、最大公约数、最下公倍数、质因数分解

2013-08-18 11:20:43

素数、最大公约数、最下公倍数、质因数分解都是与素数相关的，解决了素数的问题，其他的都可以此为基础求解。

小结：

1. 求1到n之间的素数的基本方法是通过遍历2到sqrt(n)，判断每个数是否是素数来得到，但这种方法效率很低；比较高效的解法是通过筛选法求解，如下面代码中函数GetPrimeUnderNBySieve；
2. 最大公约数可通过GCD递归定理求解，通俗的说法就是辗转相除法，《算法导论》中有详细的说明；
3. 最下公倍数可通过最大公约数得到，公式为：LCM(a,b) = a*b / GCD(a,b)；
4. 质因数分解可通过质数表得到，如下面代码中函数GetPrimeFactorByPrimeTable所示；
5. 另外，最后一种因数分解代码是最简练的，如函数Decomposition所示：

void Decomposition(int nNum)
{
    for(int i=2;i<nNum;)
    {
        if(nNum % i == 0)
        {
            nNum = nNum /i;
            cout<<i<<",";
        }
        else
        {
            i++;
        }
    }
    if(1<nNum)
        cout<<nNum<<endl;
}

注意几点：

• 可以用乘法代替开方，进行循环结束的判断

i * i <= num

• 删选法时，筛子的下标变化可以通过相加或相乘来实现，如下：

相乘：

for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
    {
        if (primeFlagArray[primeIndex])
        {
            for (sieveIndex = 2;sieveIndex * primeIndex <= number;++sieveIndex) //sieveIndex * primeIndex <= number
            {
                primeFlagArray[sieveIndex * primeIndex] = false;
            }
        }
    }

相加：

for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
    {
        if (primeFlagArray[primeIndex])
        {
            for (sieveIndex = primeIndex + primeIndex;sieveIndex <= number;sieveIndex += primeIndex) //sieveIndex * primeIndex <= number
            {
                primeFlagArray[sieveIndex] = false;
            }
        }
    }

代码（包含测试，暂时没有发现错误，欢迎交流指正！）：

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


//显示数组元素
void DisplayArray(size_t *array,size_t len)
{
    assert(array != NULL);
    for (size_t index = 0;index < len;++index)
    {
        cout<<array[index]<<"\t";
    }
    cout<<endl;
}

//判断一个数是否为质数
bool IsPrime_basic(size_t num)
{
    assert(num >= 2);
    for (size_t i = 2;i < num;++i)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

//判断一个数是否为质数
bool IsPrime_improve(size_t num)
{
    assert(num >= 2); 
    //for (size_t i = 2;i < sqrt(num);++i) // ambiguous call to overloaded function
    for (size_t i = 2;i < (int)sqrt((double)num);++i)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

//判断一个数是否为质数
bool IsPrime(size_t num)
{
    assert(num >= 2);
    for (size_t i = 2;i * i <= num;++i)  //i * i <= num而非i * i < num
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

//用筛选法求素数
size_t GetPrimeUnderNBySieve(size_t number,size_t *primeArray)
{
    assert(primeArray != NULL);

    size_t primeIndex = 0;
    size_t sieveIndex = 0;
    size_t primeCounter = 0;
    bool *primeFlagArray = new bool[number + 1];//number + 1
    size_t index;

    for (index = 2;index <= number;++index)  //index从2开始，而非从0开始；index <= number，而非index < number
    { 
        primeFlagArray[index] = true;
    }

    //memset(primeFlagArray,1,sizeof(bool) * number);

    for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
    {
        if (primeFlagArray[primeIndex])
        {
            for (sieveIndex = 2;sieveIndex * primeIndex <= number;++sieveIndex) //sieveIndex * primeIndex <= number
            {
                primeFlagArray[sieveIndex * primeIndex] = false;
            }
        }
    }

    for (index = 2;index <= number;++index)    //index <= number
    {
        if (primeFlagArray[index])
        {
            primeArray[primeCounter++] = index;
        }
    }
    delete [] primeFlagArray;
    return primeCounter;
}

//用筛选法求素数
size_t GetPrimeUnderNBySieve_2(size_t number,size_t *primeArray)
{
    assert(primeArray != NULL);

    size_t primeIndex = 0;
    size_t sieveIndex = 0;
    size_t primeCounter = 0;
    bool *primeFlagArray = new bool[number + 1];//number + 1
    size_t index;

    for (index = 2;index <= number;++index)  //index从2开始，而非从0开始；index <= number，而非index < number
    { 
        primeFlagArray[index] = true;
    }

    //memset(primeFlagArray,1,sizeof(bool) * number);

    for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
    {
        if (primeFlagArray[primeIndex])
        {
            for (sieveIndex = primeIndex + primeIndex;sieveIndex <= number;sieveIndex += primeIndex) //sieveIndex * primeIndex <= number
            {
                primeFlagArray[sieveIndex] = false;
            }
        }
    }

    for (index = 2;index <= number;++index)    //index <= number
    {
        if (primeFlagArray[index])
        {
            primeArray[primeCounter++] = index;
        }
    }
    delete [] primeFlagArray;
    return primeCounter;
}

//用递归法求GCD
size_t GetGCDByRecursion(size_t a,size_t b)
{
    if (b ==0)
    {
        return a;
    }
    
    return GetGCDByRecursion(b,a % b);
}

//用循环求GCD
size_t GetGCDByIteration(size_t a,size_t b)
{
    size_t aTmp = 0;
    while (b != 0)
    {
        aTmp = a;
        a = b;
        b = aTmp % b;
    }

    return a;
}

//用GCD求LCM，LCM(a,b) = a*b / GCD(a,b) 
size_t GetLCM(size_t a,size_t b)
{
    return ( (a * b) / GetGCDByRecursion(a,b) );
}

//求一个质数的下一个质数
size_t GetNextPrime(size_t currentPrime)
{
    int curNum = currentPrime + 1;
    while ( !IsPrime(curNum) )
    {
        ++curNum;
    }
    return curNum;
}

//根据质数表求质因数分解
void GetPrimeFactorByPrimeTable(size_t num,size_t *primerFactor,size_t *pCnt)
{
    *pCnt = 0;
    if ( IsPrime(num))
    {
        primerFactor[(*pCnt)++] = num;
        return;
    }

    size_t *primeArray = new size_t[num];
    size_t primeCounter = 0;
    primeCounter = GetPrimeUnderNBySieve_2(num,primeArray);

    cout<<"the number of primes under "<<num<<" is :"<<primeCounter<<",they are :"<<endl;
    DisplayArray(primeArray,primeCounter);

    assert(primeCounter <= num);
    size_t index = 0;

    //for (index = 2;index * index < num;++index)
    //while (index < primeCounter)
    while (primeArray[index] <= num)
    {
        if (num % primeArray[index] == 0)
        {
            primerFactor[(*pCnt)++] = primeArray[index];
            num = num / primeArray[index];
            index = 0;

            //if ( IsPrime(num))
            //{
            //    primerFactor[(*pCnt)++] = num;
            //    return;
            //}
        }
        else
        {
            ++index;
        }
    }

    delete [] primeArray;
}

//质数为自然数，所以此处的输入num为不小于最小质数2的自然数
//输入参数：num，待处理数字
//    primerFactor，存放num的质因数的数组的首地址
//    pCnt，存放数组长度的空间的地址
void GetPrimeFactor(size_t num,size_t *primerFactor,size_t *pCnt)
{
    assert(num >= 2);
    *pCnt = 0;
    const size_t MinPrime = 2;
    size_t currentPrime = 0;
    while ( !IsPrime(num)  )
    {
        currentPrime = MinPrime;
        while (num > currentPrime )  //num 不可能等于 currentPrime ，因为有外层while条件的保证
        {
            if (num % currentPrime == 0)  //从最小的质数开始，判断是否为num的因数，若不是判断下一个质数
            {
                primerFactor[(*pCnt)++] = currentPrime;
                num = num / currentPrime;
                break;
            }
            else
            {
                currentPrime = GetNextPrime(currentPrime);  //求当前质数的下一个质数
            }
        }
    }
    primerFactor[(*pCnt)++] = num;  //写入最后一个质因数
}

//直接求质因数分解
void Decomposition(int nNum)
{
    for(int i=2;i<nNum;)
    {
        if(nNum % i == 0)
        {
            nNum = nNum /i;
            cout<<i<<",";
        }
        else
        {
            i++;
        }
    }
    if(1<nNum)
        cout<<nNum<<endl;
}

//测试
void TestGetPrimeUnderN()
{
    size_t number = 0;
    size_t *primeArray = NULL;
    size_t primeCounter = 0;
    cout<<"TestGetPrimeUnderN..."<<endl;
    cout<<"please enter a number(end with ctrl + z)"<<endl;
    while (cin>>number)
    {
        primeArray = new size_t[number];
        //primeCounter = GetPrimeUnderNBySieve(number,primeArray);
        primeCounter = GetPrimeUnderNBySieve_2(number,primeArray);
        cout<<"the number of primes under "<<number<<" is :"<<primeCounter<<",they are :"<<endl;
        DisplayArray(primeArray,primeCounter);
        cout<<"please enter a number(end with ctrl + z)"<<endl;
        delete [] primeArray;
    }
}

void TestGetGCDAndLCM()
{
    size_t a = 0;
    size_t b = 0;

    
    cout<<"TestGetGCD..."<<endl;
    cout<<"please enter two numbers(end with ctrl + z)"<<endl;
    while (cin>>a>>b)
    {
        cout<<"(GetGCDByRecursion)the GCD of "<<a<<" and "<<b<<" is : "<<GetGCDByRecursion(a,b)<<endl;
        cout<<"(GetGCDByIteration)the GCD of "<<a<<" and "<<b<<" is : "<<GetGCDByIteration(a,b)<<endl;
        cout<<"the LCM of "<<a<<" and "<<b<<" is : "<<GetLCM(a,b)<<endl;
        cout<<"please enter two numbers(end with ctrl + z)"<<endl;
    }
}

//测试代码
void TestDriverGetPrimeFactor()
{
    const size_t MaxNumberOfPrimeFactor = 100;
    size_t primerFactor[MaxNumberOfPrimeFactor];
    size_t Cnt = 0;
    //size_t *pCnt = &Cnt;   //不能不定义Cnt，而直接用*pCnt
    size_t num;

    cout<<"please enter a number(end with ctrl + z)"<<endl;
    while (cin>>num)
    {
        //GetPrimeFactor(num,primerFactor,pCnt );
        GetPrimeFactorByPrimeTable(num,primerFactor,&Cnt);
        cout<<"the prime factor of number "<<num<<" is :"<<endl;
        DisplayArray(primerFactor,Cnt);

        Decomposition(num);
        cout<<"please enter a number(end with ctrl + z)"<<endl;
    }
}

//main
int main()
{
    TestDriverGetPrimeFactor();
    //TestGetPrimeUnderN();
    //TestGetGCD();
    return 0;
}