[LEVEL1][JAVA] 소수 찾기

프로그래머스

---

[LEVEL 1 ] 소수 찾기

사용 언어 : JAVA

---

# 문제

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

# 해결

package programmers.q12921;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 10;
        System.out.println(solution.solution(n));
    }
}

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 2; i <= n; i++) {
            boolean isDecimal = true;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    isDecimal = false;
                    break;
                }
            }
            if (isDecimal) {
                answer++;
            }
        }
        return answer;
    }
}

처음에는 위 방식 처럼 했는데, 정상적으로 동작은 하지만, 시간 초과가 떴다..

고민하다가 공식이 있는지 알아보다가 '에라토스테네스의 체' 라는 소수 찾기 알고리즘이 있다는 것을 알고 이해를 하고 적용시켜 보았다.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 10;
        System.out.println(solution.solution(n));
    }
}

class Solution {
    public int solution(int n) {
        List<Boolean> prime = new ArrayList<>();

        prime.add(false); // 0
        prime.add(false); // 1

        for (int i = 2; i <= n; i++) {
            prime.add(i, true);
        }

        for (int i = 2; (i * i) <= n; i++) {
            if (prime.get(i)) {
                for (int j = i * i; j <= n; j += i) {
                    prime.set(j, false);
                }
            }
        }

        return (int)prime.stream().filter(e -> e.booleanValue()).count();
    }
}

완벽하다 생각하고 제출했는데 효율성 테스트에서 실패....

물론, 처음에 적용시킨 코드 보다는 월등히 빠르다.

적용 전	적용 후

문제를 푼 학원 동기들에게 물어보니 다들 더 빠른 다른 언어(C++, javascript)들로 풀었다고 한다.

일단은 '에라토스테네스의 체'를 적용시킨것에 만족하고 나중에 고민해봐야겠다. 

# 참고

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