Lv.1 소수찾기

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

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

기본틀

class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

첫번째 시도

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        if(n == 1){
            answer = 0;
        }else{
            for(int i = 2; i < n+1; i++){
                int count = 0;
                for(int j = 1; j < i+1; j++){
                    if(i%j == 0){
                        count++;
                    }
                }
                if(count == 2){
                   answer++;
                }
            } 
        }
        
        return answer;
    }
}

정확성 테스트 10, 11, 12 와 효율성 테스트 실패!

질문하기를 보니까 '에라토스테네스의 체'를 사용하라는데... 내일 검색해봐야겠다!

 

두번째 시도 (에라토스테네스의 체 적용)

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int[] arr = new int[n+1];
        for(int i = 0; i < arr.length; i++){
            arr[i] = i;
        }
        
        arr[1] = 0;
        
        
        for(int i = 2; i < arr.length; i++){
            if(arr[i] == 0) continue;
            
            for(int j = i*2; j < arr.length; j = j+i){
                    arr[j] = 0;
            }
            
        }
        
        
        for(int i = 2; i < arr.length; i++){
            if(arr[i] != 0){
                answer++;
            }
        }
        
        return answer;
    }
}

후 드디어 성공!!!

- 에라토스테네스의 체: https://namu.wiki/w/에라토스테네스의%20체

에라토스테네스의 체 - 나무위키

소수의 배수를 다 지우는 방식!

코드는 수를 배열에 넣고 소수의 배수는 0으로 만들도록 짰다.