프로그래머스 1단계 - 소수 찾기

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

코딩테스트 연습 - 소수 찾기

 

import java.util.*;

//1~n까지 모든 수를 n이하의 수로 나눴더니...시간초과가 나왔다..
//알아보니 에라토스네테스의 체 라는것이 있엇다..!
class Solution {
  public int solution(int n) {
    int answer = 0;
    //n+1만큼 배열을 생성한다
    boolean[] sosu = new boolean[n + 1];
    //2의배수 3의배수 4의배수 .... 를 false로 만든다
    //true면 소수가아니고 false면 소수다
    //boolean의 초기값음 false이기때문에
    //처음에 2는 false기때문에 count를 1개 올리고 뒤의 2의 배수들을 true로 만든다.
    //그다음 3은 false기때문에 count를 1개 올리고 뒤의 3의 배수들은 true로 만든다.
    //그다음 4는 true기때문에 count를 올리지않고 4의 배수들을 true로 만든다
    //이렇게 n까지 반복...
    for (int i = 2; i <= n; i++) {
        //checked[i]가 소수면 + 시킨다.
        if (!sosu[i]){
            answer++;
        }
        for (int j = i; j <= n; j += i) {
            if (!sosu[j]){
                sosu[j] = true;
            }
        }
    }      
  return answer;
  }
}