[Programmers] 소수 찾기 - 연습문제

// 소수 찾기 - 연습문제
public class CountPrimeNum { // 에라토스테네스의 체 활용

	public int solution(int n) {

		int answer = 0;

		int[] arr = new int[n + 1];

		for (int i = 2; i < arr.length; i++) { // int 타입의 배열을 초기화 하고 아무값도 넣지 않으면 0으로 초기화 되므로 arr[0], arr[1]는 0이다.
			arr[i] = i;
		}

		for (int i = 2; i <= Math.sqrt(n); i++) { // i는 n의 제곱근 까지만 계산해도 됨 (효율성)

			for (int j = i * 2; j <= n; j += i) {

				if (arr[j] == 0) { // continue; 를 통해 아래의 불필요한 중복계산을 줄여준다.
					continue;
				}
				arr[j] = 0; // 2, 3 ... 의 배수(소수가 아닌수)를 0으로 치환 - 아무 값을 넣지 않은 arr[0], arr[1]이 0 으로 초기화가 돼있으므로 0으로 치환 
			}

		}
		for (int ele : arr) {
			if (ele != 0) { // 0 이 아닌 값 (소수) 카운트. int 타입의  배열을 초기화 하고 아무값도 넣지 않으면 0으로 초기화 되므로 arr[0], arr[1]는 0이다. 만약 0이 아닌 다른 수로 치환해서 이 문제를 푼다면 배열의 index=2부터 카운트해서 문제를 해결하면 된다.
				answer++; 
			}
		}
		return answer;
	}

	public static void main(String[] args) {

		CountPrimeNum s = new CountPrimeNum();
		System.out.println(s.solution(10));
		System.out.println(s.solution(5));

	}

}

• 에라토스테네스의 체 활용하기.
• list 또는 map을 쓰면 remove, get, put 등등에서 시간을 많이 허비함 (효율성X)
• 소수를 체크할때 나누는 수는 n의 제곱근 까지만 증가시키면 됨 (효율성)