프로그래머스 Lv2 숫자 블록(소수)

나는 이 문제를 1'000'000'000보다 작거나 현재 블록 보다 작지만 가장 큰 약수를 구하는 문제로 이해했다.
예를들어 18번째 위치에 있는 블록을 생각해보자.

"1, 2, 3, 6, 9, 18"의 블록이 18번째에 올 수 있다.
 
나중 블록이 이전에 깔린 블록을 덮으므로 18번째 블록은 9이다.

여기서 "1"은 약수가 아니므로 가장 큰 약수는 "2"로 나눈 "9이다" (18 / 2 = 9)

결국 처음에 오는 가장 작은 약수로 18번째를 나누면 되는 문제이다.

하지만 조건에 블록이 "1'000'000'000' 을 초과하면 안된다 하므로 가장 큰 약수를 구하는 조건에 추가했다.

또한 소수인 경우에 약수는 1이므로 가장 큰 약수를 찾지 못했을 땐 약수 1을 추가한다.

1번째에는 0의 블록이 들어가므로 begin - end가 1을 포함하면 블록 "0"을 별도로 추가했다.

마지막으로 약수 검사는 sqrt(num)을 사용했다. (sqrt(num)을 초과하면 중복되는 수를 검사하므로)

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    
    for(long long n = begin; n <= end; ++n)
    {
        if(n == 1)
        {
            answer.push_back(0);
            continue;
        }
        
        bool bFind = false;
        
        for(int i = 2; i <= sqrt(n); ++i)
        {
            if(n % i == 0 && n / i <= 1'000'000'000)
            {
                bFind = true;
                answer.push_back(n / i);
            }
        }
        
        if(!bFind)
            answer.push_back(1);
    }
    return answer;
}

문제가 어려운것은...복기를 반드시 해야겠다...