[백준 1038번 문제, JAVA] 제곱 ㄴㄴ 수

문제

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        long min = Long.parseLong(input[0]);
        long max = Long.parseLong(input[1]);

        boolean[] eratosthenes = new boolean[(int) (max - min + 1)];

        for (long i = 2; i <= Math.sqrt(max); i++) {
            long square = i * i;
            long start = min % square == 0 ? min / square : min / square + 1;
            for (long j = start; j * square <= max; j++) {
                if (j * square >= min) {
                    eratosthenes[(int) (j * square - min)] = true;
                }
            }
        }

        int answer = 0;
        for (boolean b : eratosthenes) {
            if (!b) {
                answer++;
            }
        }

        System.out.println(answer);
        br.close();
    }
}

---

해결

솔직히 챗gpt랑 tabnine이 90퍼는 다풀었음

 

1. long 형식의 인덱스를 사용하는 배열을 사용하려면 어떻게 해야하나 -> boolean[] 배열을 사용하면 됩니다

아니 왜 처음부터 이걸 쓸생각을 안했지

 

2. 시작 인덱스가 에러가 나는거같에 ->

long start = min % square == 0 ? min / square : min / square + 1;

이렇게 쓰면 확정적으로 배수의 처음 시작하는 숫자로 받을 수 있습니다

 

....

진짜 프로그래머 못해먹겠네 ㅋㅋㅋㅋ

---

솔찌 내가 생각한 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        long min = Long.parseLong(input[0]);
        long max = Long.parseLong(input[1]);

        HashMap<Long, Boolean> hash = new HashMap<>();

        for (long i = min; i <= max + 1; i++) {
            hash.put(i, true);
        }

        for (long i = 2; i <= Math.sqrt(max); i++) {
            long square = i * i;
            long start = min % square == 0 ? min / square : min / square + 1;
            if(hash.get(start)) {
                for (long j = start; j * square <= max; j++) {
                    hash.put(j * square - min, false);
                }
            }
        }

        int answer = 0;
        for (Map.Entry<Long, Boolean> entry : hash.entrySet()) {
            if (entry.getValue()) {
                answer++;
            }
        }

        System.out.println(answer);
        br.close();
    }
}

사실 이것도 탭나인이 거의 도와준거긴 한데

처음에는 ArrayList로 풀려다가 인덱스에는 Integer 형식만 올 수 있다고 해서 그러면 해쉬를 쓰는 방법은 안되려나 하고 이걸로 해봤는데 이것도 최대 개수에는 Integer 개수만큼만 되나보다 엄청 많은 수가 오면 이전의 수가 사라지는듯 그래서 널포인터 에러가 발생한다

 

그래서 틀렸습니다~

---

참고

https://youtu.be/9rLFFKmKzno?t=402