프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/12921

이전에 했던 리스트를 통한 에라토스테네스의 체를 통한 풀이는 속도가 느려 통과가 안되는 문제가 발생했다
따라서 배열을 통해 속도를 좀 더 높힐 수 있도록 했다.

1. 문제

소수 찾기

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하기

소수란?

• 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
• 1은 소수가 아니다.

2. 문제분석

1. n의 값을 입력받는다.
2. boolean 배열을 통해 사이즈를 채워넣는다.
3. 배열을 true로 모두 채워넣는다.
4. 1~n 사이의 소수를 구하기 위해 여러가지 식을 대입하여 숫자를 나눠 소수가 아닌값은 false를 대입한다.
5. true인 값을 가진 index를 카운트하여 소수의 개수를 구한다.

---

🚫 제한조건 1. n은 2이상 1000000이하의 자연수입니다.

3. 설계

(1) 에라토스테네스의 체를 이용한다.

• 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법
• 소수가 아닌 값을 제외시켜 최종적으로 소수인 값만 남기는 방식
• 이전에 했던 리스트를 통한 풀이보다 배열를 통한 풀이가 좀 더 속도가 빠름

① 2를 제외한 2의 배수를 제거

② 3를 제외한 3의 배수를 제거

③ 4는 이미 제거 되었으므로 생략

④ 위의 과정을 원하는 수만큼 반복

(2) 배열로 구현

• n번까지의 소수를 찾고싶을때
  ① 0~n까지의 크기만큼 배열을 생성후 초기화

<boolean[] result = new boolean[num+1];    // 0~n까지 크기
Arrays.fill(result,true);       // 배열 true로 채움(boolean 배열의 초기값은 false라 굳이 안채워줘도 되지만 라이브러리 사용을 위해 사용)

// 0과 1은 소수가 아니므로 false를 넣어준다.
result[0] = false;
result[1] = false;

② 2부터 50까지 돌면서 그 수를 제외한 배수를 제거

// n의 제곱근보다 작은 정수의 배수들만 지우면 n보다 작은 소수만 남게 됨
for(int i= 2; i*i<=num; i++){         // 2~7까지의 배수값 구함    7*7 = 49
            
// j = i*i로 해줘야 자기 자신값은 제외가 됨. 2,3,5,7은 소수이므로 자기 자신의 값은 제외해야함
// ex) i=2일때, 2는 소수이므로 4부터 시작하여 4,6,8,10... 값을 false로 대입
// i=4일때, 어차피 4는 i=2일때 false를 대입했으므로 자기 자신의 값을 신경안써줘도 됨
for(int j =i*i; j<result.length; j+=i){
    result[j] = false;
    }
}

③ 최종적으로 남은 리스트 사이즈를 반환

int count = 0;
for(int i=0; i<result.length; i++){
    if(result[i] == true)
       count++;
}

4. CODE

import java.util.Arrays;

/* 프로그래머스 소수찾기 (에라토스테네스의 체를 통한 풀이)
    이전에 했던 리스트를 통한 에라토스테네스의 체를 통한 풀이는 속도가 느려 통과가 안되는 문제가 발생했다
    따라서 배열을 통해 속도를 좀 더 높힐 수 있도록 했다.
 */
public class PrimeNumber {
    public int solution(int num) {

        int count = 0;
        boolean[] result = new boolean[num+1];    // 0~n까지 크기
        Arrays.fill(result,true);       // 배열 true로 채움(boolean 배열의 초기값은 false라 굳이 안채워줘도 되지만 라이브러리 사용을 위해 사용)


        // 0과 1은 소수가 아니므로 false를 넣어준다.
        result[0] = false;
        result[1] = false;

        // n의 제곱근보다 작은 정수의 배수들만 지우면 n보다 작은 소수만 남게 됨
        for(int i= 2; i*i<=num; i++){         // 2~7까지의 배수값 구함    7*7 = 49
            
            // j = i*i로 해줘야 자기 자신값은 제외가 됨. 2,3,5,7은 소수이므로 자기 자신의 값은 제외해야함
            // ex) i=2일때, 2는 소수이므로 4부터 시작하여 4,6,8,10... 값을 false로 대입
            // i=4일때, 어차피 4는 i=2일때 false를 대입했으므로 자기 자신의 값을 신경안써줘도 됨
            for(int j =i*i; j<result.length; j+=i){
                    result[j] = false;
            }
        }

        for(int i=0; i<result.length; i++){
            if(result[i] == true)
                count++;
        }

        return count;
    }

    public static void main(String[] args) {
        PrimeNumber pm = new PrimeNumber();
        PrimeNumber pm2 = new PrimeNumber();
        System.out.println(pm.solution(10));
        System.out.println(pm2.solution(5));
    }
}