에라토스테네스의 체
- 특정 범위 내의 소수를 찾을 때 사용하는 방법이다.
1. 1부터 N까지의 배열을 만든다. -> ex. int[] arr = {0,0,0,0,0,0,.....};
2. 소수가 아닌 1은 제거한다.
3. N까지 반복문을 돌려주면서 int[i] = 0인 값들에서 count++ 해준다.
- 2에서 count++;
- 2의 배수는 모두 값을 1로 바꿔준다.
- 3에서 count++;
- 3의 배수는 모두 값을 1로 바꿔준다.
- 4의 배수는 2의 배수를 1로 바꿔주는 과정에서 바뀌었기 때문에 넘어간다.
....
- 마지막에 count를 출력해주면 그 값이 1부터 N까지의 소수 개수
에라토스테네스 체 사용
public static int solution(int n){
int count = 0;
int[] check = new int[n+1];
for(int i=2; i<=n; i++){
if(check[i]==0){
count++;
// i의 (j+i)배수들을 체크해준다.
for(int j=i; j<=n; j=j+i){
check[j] = 1;
}
}
}
return count;
}
소수 판별 코드
public static boolean isPrime(int num){
if(num==1) return false; // 1은 소수가 아니다.
for(int i=2; i<num; i++){
if(num%i==0){ // i는 num의 약수가 된다.
return false;
}
}
return true;
}
'코딩테스트 > Java' 카테고리의 다른 글
[JAVA] 유클리드 호제법 - 최대 공약수, 최대 공배수 (0) | 2022.06.24 |
---|---|
[JAVA] 2차 배열 행과 열의 합, 대각선의 합 구하기 (0) | 2022.06.24 |
[JAVA] 정수 한자리씩 쪼개기 (0) | 2022.06.24 |
[JAVA] 정렬 - Arrays.sort(), Collections.sort(), CompareTo (0) | 2022.06.23 |
[JAVA] next(), nextLine() 차이점 (0) | 2022.06.23 |