[ 프로그래머스 ] 소수 찾기 JAVA

 

소수 찾기

 

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

   

입출력 예

10	4
5	3

 

입출력 예 설명

입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

class Solution {
  public int solution(int n) {
		int answer = 0;
		boolean[] checked = new boolean[n + 1];

		for (int i = 2; i <= n; i++) {
			if (!checked[i])
				answer++;
			for (int j = i; j <= n; j += i) {
				if (!checked[j])
					checked[j] = true;
			}
		}      
      return answer;
  }
}

 

 

이전에 공부했었던 에라토스테네스의 체를 활용하여 풀이하였습니다.

 

**에라토스테네스의 체에 대해 알고 있다면 풀이에 도움이 될 것 같아 관련 자료를 찾아보았습니다.**

 


 

**출처 : 위키백과**

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

**먼저 소수를 찾기 위해 boolean 배열 checked를 만들었습니다.**

 

**그리고 나서, 2부터 n까지 i의 만큼씩 더해 반복하며 소수에 해당하지 않는 수는**

 

**checked 배열에 true 처리하여 표시해주었습니다. ( 에라토스테네스의 체와 유사하게 )**

 

**모두 표시해준 이후 checked 배열이 false인 숫자들만 카운트 해주었습니다.**

 

 

 

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

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