소수 찾기-에라토스테네스-백준 17103

며칠동안 끙끙대던 문제를 가져왔따.

이 문제를 풀어보겠습니다.

---

처음에는 그저 앞에서 했던 소수문제들하고 별 다를거 없다고 생각했따. 시간이 매우 촘촘한것 빼고는,,(이게 문제였음)

for (int j = 2; j < N; j++) {
    boolean isPrime = true;
    for (int k = 2; k <= Math.sqrt(j); k++) {
        if (j % k == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        arrayList.add(j);
    }
}

 

하지만 특정 범위까지의 소수만 더해서 값을 비교하기 위해서 list를 사용했다.

이렇게 하니까 시간이 매우 많이 걸렸따. 출력 코드는

            for (int j = 0; j < arrayList.size(); j++) {
                    for (int k = j; k < arrayList.size(); k++) {
                        if (arrayList.get(j) + arrayList.get(k) == N) {
                            cnt++;
                        }
                    }
            }

이렇게 했는데,  j부터 + j를 세고 난 후 부터의 합으로 하는것ㅎ,,,, 

---

문제점은 시간이 너무 오래걸린다는것,

소수를 효율적으로 담아둘 수 있는 방법이 필요했다.

---

정답 코드

package math2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Q8 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int A = 1000001;
        boolean[] isPrime = new boolean[A];
        Arrays.fill(isPrime, true);

        for (int j = 2 ; j <= Math.sqrt(A) ; j++) {
            if (!isPrime[j]) continue;
            int idx = 2;
            while (j * idx <= A - 1) {
                isPrime[j * idx] = false;
                idx++;
            }
        }


        for (int i = 0; i < T; i++) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int N = Integer.parseInt(br.readLine());
            for (int j = 2 ; j <= N ; j++) {
                if (isPrime[j]) arrayList.add(j);
            }

            int cnt = 0;
            int j = 0, k = arrayList.size() - 1;
            while (j <= k) {
                if (arrayList.get(j) + arrayList.get(k) < N) {
                    j++;
                } else if (arrayList.get(j) + arrayList.get(k) > N) {
                    k--;
                } else if (arrayList.get(j) + arrayList.get(k) == N) {
                    cnt++;
                    j++;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

 

우선 사이즈가 1,000,001의 boolean배열을 만든다. 이유는 1,000,000까지가 범위이고, 백만 전까지의 모든 소수를 담아두기 위해서이다.

 

그 다음, 모든 배열을 true로 채운다.(배열 이름이 isPrime이니까.)

for (int j = 2 ; j <= Math.sqrt(A) ; j++) {
    if (!isPrime[j]) continue;
    int idx = 2;
    while (j * idx <= A - 1) {
        isPrime[j * idx] = false;
        idx++;
    }
}

여기가 중요한데,

에라토스테네스의 채를 응용해보면, 2의 배수, 3의 배수, 4의 배수,,,, 등등

목표로 하는 수(1,000,000) 가

x의 제곱,x+1의 제곱 사이에 위치하면 

본인을 제외한 x의 배수들을 목표로 하는 수(1,000,000) 전까지 false로 바꿔주면은,

남는 수는 2,3,5,7,11,..... 소수만 남게 된다.

---

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체

---

자 다시 돌아와서,

j가 A의 제곱근과 같거나 작을때,

배수들을 구해보는데, (1,000,000 전까지)

이 인덱스의 isPrime배열을 false로 바꿔준다. (소수가 아니니까.)

만약, j에 해당하는 isPrime이 이미 fasle라면, 거긴 지워진 곳이니까 continue해준다.

---

매우 큰 산을 넘었다.

이제 isPrime이 참인 곳의 인덱스(j)를 list에 추가해주면 소수로만 이루어진 리스트가 만들어진다.

 

for (int i = 0; i < T; i++) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    int N = Integer.parseInt(br.readLine());
    for (int j = 2 ; j <= N ; j++) {
        if (isPrime[j]) arrayList.add(j);
    }

    int cnt = 0;
    int j = 0, k = arrayList.size() - 1;
    while (j <= k) {
        if (arrayList.get(j) + arrayList.get(k) < N) {
            j++;
        } else if (arrayList.get(j) + arrayList.get(k) > N) {
            k--;
        } else if (arrayList.get(j) + arrayList.get(k) == N) {
            cnt++;
            j++;
        }
    }
    sb.append(cnt).append("\n");
}

이제는 출력하는 것의 코드이다.

이 또한 중요하다.

결국에 개념은 

맨 좌측과 맨 우측에 포인터를 각각 둔다,

j번째와k번째의 합을 구하는데 

만약, 합이 N보다 작으면?-----------------> 맨 좌측의 값을 한칸 올려야지~~~~~~~~~~

만약, 합이 N보다 크면?--------------------->맨 우측의 값을 한칸 내려야지~~~~~~~~~~

만약, 합이 N이야!!!!!!!------------------------>개수 카운트 해주고, 맨 좌측 포인터 다시 이동~

단,,,,,,,,,,,,,,,,,,,,,,,,,,,,

 

맨 좌측 포인터가 우측 포인터를 넘어가는 순간!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

종료!!

 

이렇게 해서 풀어봤다.

아주 흥미롭고 많은걸 배워가는 문제였다.

앞으로 내가 스스로 머릿속에서 생각이 솟아나오도록 저장해본다.