[프로그래머스] Level 2. 숫자 블록

 

https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스

 

 

1. 각 블록에는 자신의 약수 중 가장 큰수를 저장한다.

2. 수는 10,000,000보다는 작아야한다.

 

약수를 검사하는 횟수를 최대한 줄이기 위해서 , 숫자의 제곱근에서 시작한다. 약수 i를 찾고, i와 짝이되는 slot/i  두 숫자를 검사한다.

만약 slot/i 가 MAX보다 작다면 그 수가 가장 큰 약수이다.

아니라면 다음 약수 짝을 검사한다.

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer(end-begin+1, 0);
    long long MAX = 10000000;
    
    for(int slot = begin; slot<=end; slot++){
        if(slot ==1)continue;
        
        int value = 1;
        for(int i=2; i<= sqrt(slot); i++){
            if(slot%i!=0) continue;
            if(slot/i<=MAX){
                value = slot/i; //최대약수찾았음.
                break;
            }
            value= i; //작은거라도 우선 넣음.
        }
        
        answer[slot-begin] = value;
    }
    return answer;
}