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

문제 출처 :

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

문제 :

 

소스코드 :

import java.util.*;
class Main {
	public int solution(long min, long max) {
		int answer = 0;
		// min부터 max까지의 배열을 생성한다.
		long len = (int)(max-min)+1;
		long arr[] = new long[(int)len];
		// 에라토스테네스 체 알고리즘을 응용해 1보다 큰 제곱수로 나누어 떨어지는 수들을 골라낸다.
		for (long i=2; i*i<=max; i++) {
			long squ = i * i; // 제곱값
			long quo = min / squ; // 몫
			if (squ * quo < min) { // 제곱값*몫이 min보다 작을 경우 몫++
				quo++;
			}
			// 해당 위치의 인덱스를 찾는다.
			// 예를 들면 i=2일 때, 5부터 20까지 배열 중에서 8에 해당하는 인덱스 위치는
			// 4 * 2 - 5 = 3 이다.
			long t = squ * quo - min;
			for(long j = t; j<arr.length; j+=squ) {
				arr[(int)j] = 1; // 1보다 큰 제곱수로 나누어 떨어지는 수에 해당하는 배열의 값을 1로 만든다.
			}
		}
		// 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
		for (int i = 0; i < arr.length; i++) {
            if(arr[i] == 0){
                answer++;
            }
        }
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		long min = sc.nextLong();
		long max = sc.nextLong();
		System.out.println(T.solution(min, max));
	}
}

 

에라토스네테스 체를 응용하는 문제라는걸 알고 풀었는데

꽤 오랜 시간 걸렸다.

컴파일 에러가 계속 떠서 억울했는데 알고보니

long min = sc.nextInt() 이렇게 입력을 받아서 계속 컴파일 에러가 발생했던 것이다..

어이없긴 하지만 큰 교훈이 되었다.