1. Problem 📃

[ 소수 찾기 ]
https://programmers.co.kr/learn/courses/30/lessons/12921

2. Constraint 🔗

3. Solution 🔑

1. 에라토스테네스의 체 알고리즘을 사용하여 풀이를 할 것이다. (에라토스테네스의 체는 아래 설명)

2. 구하고자 하는 수까지 n까지 배열을 선언하고 0으로 초기화 한다 int[] arr = new int[n+1];

0으로 초기화하는 이유는 지워지는 수를 요소값을 1로 바꾸어 지워진것으로 표시

3. for문에 i=2부터 돌려서, 1씩 증가시켜 배수를 구해 줄 변수(cycle)를 선언 후 i * cycle < n 일때 까지 실행하면서 나온 값의 [ i * cycle] 인덱스의 값은 1로 변경.

4. n이 지워지지 않았다면 n은 소수로 판단

4. Code 💻

class Solution {
	public int solution(int n) {
		int[] arr = new int[n+1];
		int answer = 0;
		
		for(int i=2; i<=n; i++) {
			int cycle = 1;
			if(arr[i] == 0) {
				answer++;
				while(i*cycle <= n) {
					arr[i*cycle] = 1;
					cycle++;
				}
			}
		}		
		return answer;
	}
}

5. Growth 🍄

이번 문제를 풀면서 "에라토스테네스의 체"에 대해 처음 알게 되었는데

[ 에라토스테네스의 체 ]

자기가 구하고자 하는 수 n을 2부터, n-1까지의 배수들을 지워나가면서 n이 지워지지 않으면 n은 소수라고 판단하는 방법이다.