[JAVA] 프로그래머스 : 소수 찾기 (Level 1)

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java

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

해결 방안

주어진 숫자 n의 1~n 까지의 소수 갯수를 찾는 문제이다.

에라토스테네스의 체를 사용하여 i 가 소수인지 확인하였다.

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=2; i<=n; i++){
            if(i==2){
                answer++;
                continue;
            }
            
            // 소수 아님
            if(i%2==0) continue;
            
            // 소수 아님
            boolean flag = true;
            for(int j=3; j<=(int)(Math.sqrt(i)); j+=2){
                if(i%j==0) {
                    flag = false;
                    break;
                }
            }
            if(flag){
                answer++;
            }
                
        }
    
        return answer;
    }
}