728x90
난이도 - 골드 1
문제
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
입력
첫째 줄에 두 정수 min과 max가 주어진다.
출력
첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.
제한
- 1 ≤ min ≤ 1,000,000,000,000
- min ≤ max ≤ min + 1,000,000
728x90
min~max의 수가 제곱수의 배수인지 나타내는 배열을 생성한다.(isNoeSquares)
outerLoop: 2부터 루트max까지의 i의 제곱수를 계산한다.(square)
innerLoop의 시작점을 계산한다. min이 square로 나누어 떨어지면 start는 min이 되고, 그렇지 않으면 min보다 큰 수 중 가장 작은 square의 배수를 start로 한다.
innerLoop: min부터 max까지 square의 배수들을 true로 변경한다.
import java.io.*;
import java.util.StringTokenizer;
public class Main1016 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long min = Long.parseLong(st.nextToken());
long max = Long.parseLong(st.nextToken());
bw.write(String.valueOf(countNotSquare(min, max)));
bw.flush();
br.close();
bw.close();
}
static int countNotSquare(long min, long max) {
boolean[] isNotSquares = new boolean[(int) (max - min + 1)];
for (long i = 2; i * i <= max; i++) {
long square = i * i;
long start = min % square == 0 ? min : min + (square - min % square);
for (long j = start; j <= max; j += square) {
isNotSquares[(int) (j - min)] = true;
}
}
int count = 0;
for (int i = 0; i < isNotSquares.length; i++) {
if (!isNotSquares[i]) {
count++;
}
}
return count;
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 7789번(텔레프라임) - 소수 판정 (0) | 2024.06.24 |
---|---|
[백준 자바] 1644번(소수의 연속합) (0) | 2024.06.24 |
[백준 자바] 24039번(2021은 무엇이 특별할까?) - 연속한 두 소수의 곱 (0) | 2024.06.23 |
[백준 자바] 6588번(골드바흐의 추측) (0) | 2024.06.23 |
[백준 자바] 9020번(골드바흐의 추측) (0) | 2024.06.23 |