프로그래머스 level1 문제 : 소수찾기(java)

문제 설명 : 

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.

제한 조건 : 

1. strings는 길이 1 이상, 50이하인 배열입니다.
2. strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
3. strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
4. 모든 strings의 원소의 길이는 n보다 큽니다.
5. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

저도 계속해서 

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(2);
boolean isPassedIndex = true;
for(int i=3; i<=num; i++) {
    for(int j=0; j<arrayList.size(); j++) {
        if(i%arrayList.get(j) == 0) {
            isPassedIndex = false;
            break;
        }
    }
    if(isPassedIndex)
        arrayList.add(i);
    isPassedIndex = true;
}
return arrayList.size();

이를 가지고 풀었습니다. ArrayList가 가장 빠르다 생각했고 이 말고도 boolean 값으로만 해서 cnt를 세봤습니다.

하지만 위의 식은 테스트는 다 통과했지만, 효율성에서 계속 실패했습니다...

도저히 안되겠어서 구글링을 했고 우연히 에라토스테네스의 체를 알게 되었습니다.

역시 이해하기 어렵더라구요....

에라토스테네의 체란 "소수"를 찾는 방법인데, 모든 수는 소수의 곱으로 이루어졌다에서 나오는 것이라 합니다...

즉, 모든 값은 소수인 2의 곱셈, 3의 곱셈, 5의 곱셈....으로 이루어져 있어 곱들을 지우다 보면 구하는 구간의 모든 소수가 남습니다. 즉... 무식하게 하나씩 지워가는 방법입니다. 이를 이용한 식으로, C++, Java, python 으로 구현한 예제는 위키백과인

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에 담겨있습니다.

어렵죠? 쉽게 예를 들자면, 1~10까지의 소수를 알고 싶다면, 10까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 어떤 수 8 = 2x4면 2(4)와 4(2) 중 적어도 하나는 root10(=3.xxx) 이하이다. 즉 10보다 작은 합성수 8은 10보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로,  root10이하의 수의 배수만 지우면 된다.

라는 의미입니다!!!! 이해 가셨나요? 참 이쁘게도 위의 url에 지우는게 담겨있는데요!! 참고하시면 좋겠어요!!!

저도 어렵게 어렵게 이해를 하려고 노력하고 있습니다..(사실 이해 잘 안가요 저도... 옛날 방식인데 이 방식 말고는 소수에 대한 식을 구하는게 아직까지 해결 못했다고? 하네요..)

이를 참고해 아래처럼 구했습니다.

int solution(int num) {
    int result = 0;
    for(int i=2; i<=num; i++) {
        boolean isPrime = true;
        for(int j=2; j*j<=i; j++) {
            if(i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if(isPrime)
            result++;
    }
    return result;
}

j*j 대신 Math.sqrt 함수를 써서 하셔도 상관없습니다!!!

모두 이 그지같은 소수구하기는 외우도록 합시다....!!