C++笔试 - 送木板

描述

木板商开业大酬宾，免费赠送木板。老板给每个客人准备了N块木板。客人必须按以下规则去拿木板：客人每次可以拿M块木板M是N的质因数M <= 根号N。这时, 木板商就会在客人拿走M块木板后再拿走M块木板。然后客人可以接着拿木板。有一个木匠他非常想知道最多可以拿到多少块木板，请你写个程序告诉他。

输入描述

一个整数N,N <= 100000

输出描述

能拿到木板数量的最大值

样例输入 1

16

样例输出 1

8

#include <iostream>

using namespace std;

//#define UNIT_TEST

class GiftWoodenBoards
{
public:
    int GiftMaxWoodenBoards(int n);

private:
    bool checkPrime(int n);
    bool checkPrimeDivisor(int n, int m);
};

bool GiftWoodenBoards::checkPrime(int n)
{
    if (n < 2 || n % 2 == 0 && n>3)
    {
        return false;
    }

    for (int i=3; i < (int)sqrt(double(n)); i += 2)
    {
        if (n%i == 0)
        {
            return false;
        }
    }
    return true;
}

bool GiftWoodenBoards::checkPrimeDivisor(int N, int M)
{
    if (N % M == 0 && true == checkPrime(M))
    {
        return true;
    }
    return false;
}

int GiftWoodenBoards::GiftMaxWoodenBoards(int N)
{
    int sum = 0;
    int M = 2;

    while (M <= (int)sqrt((double)N))
    {
        if (true == checkPrimeDivisor(N, M))
        {
#ifdef UNIT_TEST
            cout << "N=" << N << ", M=" << M << endl;
#endif
            sum += M;
            N   -= 2*M;
            M    = 2;
        }
        else
        {
            M++;
            if (M % 2 == 0) // if M=4, 6, 8, 10, ...
            {
                M++; // M=5, 7, 9, 11, ...
            }
        }
    }

    return sum;
}
    
int main()
{
    int N;
    cin >> N;

    GiftWoodenBoards gift_wooden_boards;

    cout << gift_wooden_boards.GiftMaxWoodenBoards(N) << endl;

    return 0;
}