[프로그래머스] 소수 찾기 for JAVA (level 1) _ 에스테라토스의 체

 

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

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

 

 

 

ㅜㄴ제

 

 

---

 

옹이 생각보다 어렵네

 

 

 

에스테라토스의 체를 써야 효율성 테스트를 통과한다.

 

 

 

n개만큼 빈 boolean 배열을 만들어서

 

2~n까지 값의 배수를 true로 바꾸고

 

 

배열 속 false 개수를 세어주면 된다.

 

 

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean number[] = new boolean[n+1];
        
        for(int i = 2; i <= n; i++){
            if(number[i]) continue;
            
            for(int j = i * 2; j <= n; j += i)
                number[j] = true;
        }
        
        for(int i = 2; i <= n; i++) // 0,1은 소수 아니니까 2부터..
            if(!number[i]) answer++;
        
        return answer;
        
    }
}

 

 

 

 

음 중요한 것은 j 값의 범위를 i * 2부터 시작해야한다는 점...?

 

 

 

 

 

 

성능