[Programmers/JAVA] 소수 찾기 / 프로그래머스 코딩 테스트 연습

소수 찾기

 

---

문제 설명

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

 

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

---

예시

 

n	result
10	4
5	3

---

코드 해석 및 전체 코드

 

해석을 하지 못하겠다.

이 글을 참고하여 에라토스테네스의 체로 코드를 작성하였는데, 되지 않는다.

배열 타입을 boolean으로 잡아도 되지 않는다. 개빡

 

 

class Solution {
    public int solution(int n) {

        int answer = 0;
        int[] arr = new int[n + 1];
        
        arr[0] = arr[1] = 0;
        
        for(int i = 2; i <= n; i++)
            arr[i] = 1;
            
        for(int i = 2; i <= n; i++){
            if(arr[i] == 1)
                for(int j = i * 2; j <= n; j += i) arr[j] = 0;
            if(arr[i] == 1) {
                answer++;
            }
        }
        return answer;
    }
}

---

첫번째 실패 코드

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

---

github

programmers