[백준 1016] 제곱 ㄴㄴ 수 (JAVA)

백준 1016번 문제  - 제곱 ㄴㄴ 수 

1016번: 제곱 ㄴㄴ 수

---

문제 분석

 

• min 값과 max 값 사이 수 중에서 제곱 ㄴㄴ 수의 개수를 출력해라
  • 제곱 ㄴㄴ 수 : 정수의 제곱수의 배수가 아닌 수 (약수 중에 제곱수가 없는 수)

---

해결 키 포인트

 

• 정수론: 소수구하기 - 에라토스테네스의 체의 원리
• 배열의 사이즈를 어떻게 설정할 것인가?
  • 제약 조건 : 1 ≤ min ≤ 1,000,000,000,000 | min ≤ max ≤ min + 1,000,000
  • 한 수만 보면 매우 큰 수 같지만, 실제로 max와 min 사이 값은 1000000이므로 int 타입으로 배열 제작 가능하다
  • 즉, 배열의 사이즈는 max-min+1 이다.
• 시간 제한과 메모리 제한 - 생각보다 여유롭지 않다.
  • 시간제한: 에라토스테네스의 체의 원리를 사용하고도 더 아껴야 한다. min 값에서 max 값 사이 수만 검사하도록 코딩 해야 한다.
  • 메모리제한: boolean List를 이용해서 메모리를 최소화한다.
• 어떻게 min 값에서 max 값 사이 수만 검사하도록 코딩?
  • 제곱을 한 값의 배수를 검사할 때, min보다 크거나 같은 배수부터 max까지 반복하게
  • min 보다 크거나 같은 배수부터 : long newPow = pow * Math.max((min / pow), 1);
    (여기서 pow은 제곱 수이다) 
    
  • 이렇게 해도 min보다 안 클 수 있으므로, 예외처리도 해주기

 

---

에라토스테네스의 체의 원리

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. ( 1도 소수가 아니다 ) 

 

에라토스테네스의 체 원리 알고리즘

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성

2. 2부터 시작해 N의 제곱근까지 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다

3. 2~N의 제곱근 까지 탐색을 반복한 후 배열에서 남아있는 모든 수를 출력

 

N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 
만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다는 뜻
따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

---

코드

import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);

        // min, max 입력
        long min = sc.nextLong();
        long max = sc.nextLong();
        int range = (int) (max - min + 1);

        // 배열 생성
        boolean[] check = new boolean[range];

        for (long i = 2; i * i<= max; i++) {
            // 제곱 수
            long pow = i * i;
            // MIN보다 큰 제곱 수 알아내기
            long newPow = pow * Math.max((min / pow), 1);

            // 만약 새로 구한 제곱 수도 min보다 작을 경우 제곱 한번 더 더하기
            if (newPow < min) {
                newPow += pow;
            }

            // max 값까지 제곱수의 배수 확인하기
            for(long j=newPow;j<=max;j+=pow) {
                check[(int) (j - min)] = true;
            }
        }

        // 개수 알아내기
        int count = 0;
        for (int i = 0; i < range; i++) {
            if (!check[i]) {
                count++;
            }
        }

        System.out.println(count);
    }
}