programmers 소수 찾기

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

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

 

 

문제 분석

- 에라토스테네스의 체 알고리즘을 활용하여 소수를 구한다. (참고 : 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)

 

 

문제 풀이

1. boolean배열을 통해 해당 숫자가 소수인지 판별한다.

2. 입력받은 n의 제곱근을 구하여 해당 숫자까지만 for문을 돌려서 소수인지 판단한다.

3. 해당 숫자의 배수는 전부 true처리하고 해당 숫자는 false로 냅둔다.

4. 만약 이미 소수라면 continue를 통해 계속 진행한다.

5. for문을 통해 2부터 해당 숫자까지 소수의 개수를 체크하여 반환한다.

import java.lang.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] prime = new boolean[n+1];
        int end = (int)Math.sqrt(n);
            
        for(int i=2;i<=end;i++){
            if(prime[i]){
                   continue;
            }
            for(int j=2*i;j<=n;j+=i){
               if(prime[j]){
                   continue;
               }
               prime[j] = true; 
            }
        }
        
        for(int i=2;i<=n;i++){
            if(!prime[i]){
                answer++;
            }
        }
        
        return answer;
    }    
}

 

 

https://github.com/SOEUN2/Algorithm