문제링크

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

구현방법

구간을 나타내는 begin end를 매개변수로 주어진다.

블록의 적힌 번호가 n -> 첫블록은 n*2번째 설치

최대 10억

정답은 -> end - begin +1 의 크기만큼 받음.

시작점은 begin 끝점은 end 까지 복사

최대 천만의 숫자의 블록까지이다.

10

약수중에 본인을 제외한 가장 큰 값.

1 ~ 10000000

기본 전제 : 약수중 본인을 제외한 가장 큰 값이다.

소수인경우 -> 1 이 들어감

결국 본인의 약수 구하는 문제 -> 약수의 경우 현재 값의 제곱근 까지만 체크하면 되기 때문에 -> 처리량 감소

만약 현재값을 idx로 나눈 나머지가 0인경우

1. 나눈 idx는 일단 넣어둔다.
2. 만약 현재값을 idx로 나눈 나머지가 천만보다 작은경우 -> 작은수에서 값이 올라오는 for문이기 때문에 본인을 제외한 가장 큰 약수 값이다. -> return 해준다.
3. list가 비어있다면 -> 소수임 -> 1을 리턴해줌
4. 소수가 아니고 첫만을 넘어서는 경우에는 현재까지 쌓아둔 list의 마지막 값을 리턴해준다.

알고리즘

구현

CODE

import java.util.*;


class Solution {
    public int[] solution(long begin, long end) {

        int size = (int) (end - begin);
        int[] answer = new int[size + 1];

        for (int start = (int)begin; start <= (int)end; start++) {
            int index = (int)(start - begin);
            answer[index] = check(start);

        }
        return answer;
    }

    //공약수 구하기
    private int check(int start) {
        if(start == 1){
            return 0;
        }
        List<Integer> lists = new ArrayList<>();
        for(int idx = 2; idx <= Math.sqrt(start);idx++){
            if(start ==idx){
                continue;

            }

            if(start % idx == 0){
                lists.add(idx);
                //나눈 값이 천만보다 작은 경우 -> 최대 값임. -> 천만보다 크면 어쩌피 아웃임.
                if(start / idx <=10000000){
                    return start/idx;
                }
            }
        }

        if(!lists.isEmpty()){
            return lists.get(lists.size()-1);
        }

        //1로만 나눠지는 경우 -> 소수인 경우
        return 1;

    }
}