[프로그래머스] - 소수찾기

---

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

---

[문제 풀이]

• 해당 문제의 제한 조건을 보면 n은 2 ~ 1000000의 범위를 가진다.
• 따라서 O(n^2)의 소수판별 알고리즘을 사용하면 시간초과로 통과하지 못한다.
• 특정한 소수의 제곱근은 소수가 아니라는 특징을 가지고 O(n^1/2)의 시간 복잡도를 낼 수 있다.
• 위와 같은 방법을 에라토스테네스의 체라고 한다.

---

[java]

class Solution {
     int arr[] = new int[10000001];

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

        findPrime(n);
        
        for(int i=2; i<=n; i++){
            if(arr[i] != 0) answer++;
        }
        
        return answer;
    }

    public void findPrime(int n) {
        for(int i=2; i<=n; i++) arr[i] = i;

        for(int i=2; i<=n; i++){
            if(arr[i] == 0) continue;

            for(int j=2*i; j<=n; j+=i){
                arr[j] = 0;
            }
        }
    }
}