Level 2. 숫자 블록

Level 2. 숫자 블록

 

 

10,000,000 이하의 가장 큰 약수를 찾는 문제다.

• 수의 제곱근까지만  순회하면 되고, 약수와 수/약수를 최댓값을 구하는 데 사용하면 된다.

 

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

using namespace std;

int max_divisor(int num)
{
    if (num <= 1)
        return 0;

    int last = min(sqrt(num), 10'000'000.0);
    int maxDivisor = 1;

    for (int i = 2; i <= last; ++i)
    {
        if (num % i == 0)
        {
            maxDivisor = max(maxDivisor, i);

            int div2 = num / i;

            if (div2 <= 10'000'000)
                maxDivisor = max(maxDivisor, div2);
        }
    }

    return maxDivisor;
}

vector<int> solution(long long begin, long long end)
{
    size_t n = end - begin + 1;
    vector<int> answer(n);

    for (int i = 0; i < n; ++i)
        answer[i] = max_divisor(begin + i);

    return answer;
}

 

사실 짝수인 경우에는 가장 큰 약수가 10,000,000 이하일 경우, 2를 나눠 바로 구할 수 있다.

 

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

using namespace std;

int max_divisor(int num)
{
    if (num <= 1)
    {
        return 0;
    }
    else if (~num & 1)
    {
        int div = num >> 1;

        if (div <= 10'000'000)
            return div;
    }

    int last = min(sqrt(num), 10'000'000.0);
    int maxDivisor = 1;

    for (int i = 2; i <= last; ++i)
    {
        if (num % i == 0)
        {
            maxDivisor = max(maxDivisor, i);

            int div2 = num / i;

            if (div2 <= 10'000'000)
                maxDivisor = max(maxDivisor, div2);
        }
    }

    return maxDivisor;
}

vector<int> solution(long long begin, long long end)
{
    size_t n = end - begin + 1;
    vector<int> answer(n);

    for (int i = 0; i < n; ++i)
        answer[i] = max_divisor(begin + i);

    return answer;
}