[ Programmers ] 소수 찾기 (Java)

tpdlqj0514·2021년 4월 26일
0

Programmers

목록 보기
6/20
post-thumbnail

1. Problem 📃

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


2. Constraint 🔗


3. Solution 🔑

  1. 에라토스테네스의 체 알고리즘을 사용하여 풀이를 할 것이다. (에라토스테네스의 체는 아래 설명)
  1. 구하고자 하는 수까지 n까지 배열을 선언하고 0으로 초기화 한다 int[] arr = new int[n+1];

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

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

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


4. Code 💻


```java 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;
}

}


<br>

# 5. Growth 🍄

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

**<span style="color:rgb(0,50, 180); fontSize:20px">[ 에라토스테네스의 체 ]</span>**

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

profile
걸음마 연습중입니다.

관심 있을 만한 포스트

0개의 댓글